国产av日韩一区二区三区精品,成人性爱视频在线观看,国产,欧美,日韩,一区,www.成色av久久成人,2222eeee成人天堂

Home Java JavaInterview questions Application of merge sort in java interview

Application of merge sort in java interview

Nov 18, 2020 pm 03:41 PM
java merge sort interview

Application of merge sort in java interview

Background of the article:

While reviewing algorithms and data structures, I found the interview written test questions. Let’s take a look at the questions:

(Learning Video sharing: java teaching video)

Two numbers in the array, if the previous number is greater than the following number, then the two numbers form a reverse-order pair. Input an array and find the total number of reverse-order pairs P in the array. And output the result of P modulo 1000000007. That is, output P 00000007

Input description:

The question ensures that the same number is not in the input array

Data range:

For the data of P ,size<=10^4

For the data of u, size<=10^5

For the data of 0, size<=2*10^5

Analysis:

This question is easy to solve directly, but the time complexity is o(n*n). When I first got this question without thinking about it, I just finished writing it through DP. Then I found that DP is not as good as directly. The solution has a complexity of O(n*n), and dp also takes up 2*10^5 space. The following is direct. The solution and dp have timed out.

(Recommendations for more related interview questions: java interview questions and answers)

Code sharing:

  //直接求法 ,超時
public  class solution{
   public static  int sum;
   
   public static int InversePairs(int [] array) {
        dp(array);
        return sum;
   }
   
 
   public static void dp(int []array){
       for(int i = array.length - 1 ; i >  0 ; i --){
           for(int j = i - 1 ; j >= 0 ; j--){
                if(array[j] > array[i]){
                	sum += 1;
                } 
           }
           sum %= 1000000007;
       }
       
   }
}
public  class solution{
 
  //一維數(shù)組dp   
   public static  int sum;
   
   public static int InversePairs(int [] array) {
        dp(array);
        return sum;
   }
   public static int count[] = new int[200004];
   
   public static void dp(int []array){
       for(int i = array.length - 1 ; i >  0 ; i --){
           for(int j = i - 1 ; j >= 0 ; j--){
                if(array[j] > array[i]){
                	count[j] = count[j+1]+1;
                }else {
                	count[j] = count[j+1];
                }
           }
           sum += count[0];
           sum %= 1000000007;
           for(int k = 0 ; k < array.length ; k ++)
        	   count[k] = 0;
       }
       
   }
    
}

dp is redundant here,

The following is the solution to the problem of merge sort. If you don’t understand merge sort, you can read my previous blog MERGE SORT:

public class solution{   
    //歸并排序AC
    public static int  cnt ;
    
    public static  int InversePairs(int [] array) {
         
        if(array != null){
             RecusionSorted(array,0,array.length - 1);
        }
        return  cnt%1000000007;
    }	
	
	public static void MegerArray(int[] data, int start, int mid, int end) {
		 int temp[] = new int[end-start+1]; 
		 int i  =  mid;
		 int j = end;
		 int m = mid+1;
		 int z = 0;
		 while(j >= m && i >= start) {
			 if(data[i] > data[j]) {
				 temp[z++] = data[i--];
				 cnt += (j-mid)%1000000007;
                 cnt %= 1000000007;
			 }else {
				 temp[z++] = data[j--];
			 }
		 }
		 
		 while(j >= m) {
			 temp[z++] = data[j--];
		 }
		
		 while(i >= start) {
			 temp[z++] = data[i--];
		 }
		 
		 for(int k = start ; k <= end ; k ++) {
			 data[k] = temp[end - k];
		 }
	}
	
	public static void RecusionSorted(int data[] , int start , int end ) {
		
		
		if(start < end) {
			int mid = (start + end) >> 1;
			RecusionSorted(data,start,mid);
			RecusionSorted(data,mid+1,end);
		    MegerArray(data,start,mid,end);
		} 
	}
}

Related recommendations: java introductory tutorial

The above is the detailed content of Application of merge sort in java interview. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

PHP Tutorial
1502
276
How to handle transactions in Java with JDBC? How to handle transactions in Java with JDBC? Aug 02, 2025 pm 12:29 PM

To correctly handle JDBC transactions, you must first turn off the automatic commit mode, then perform multiple operations, and finally commit or rollback according to the results; 1. Call conn.setAutoCommit(false) to start the transaction; 2. Execute multiple SQL operations, such as INSERT and UPDATE; 3. Call conn.commit() if all operations are successful, and call conn.rollback() if an exception occurs to ensure data consistency; at the same time, try-with-resources should be used to manage resources, properly handle exceptions and close connections to avoid connection leakage; in addition, it is recommended to use connection pools and set save points to achieve partial rollback, and keep transactions as short as possible to improve performance.

Understanding the Java Virtual Machine (JVM) Internals Understanding the Java Virtual Machine (JVM) Internals Aug 01, 2025 am 06:31 AM

TheJVMenablesJava’s"writeonce,runanywhere"capabilitybyexecutingbytecodethroughfourmaincomponents:1.TheClassLoaderSubsystemloads,links,andinitializes.classfilesusingbootstrap,extension,andapplicationclassloaders,ensuringsecureandlazyclassloa

How to work with Calendar in Java? How to work with Calendar in Java? Aug 02, 2025 am 02:38 AM

Use classes in the java.time package to replace the old Date and Calendar classes; 2. Get the current date and time through LocalDate, LocalDateTime and LocalTime; 3. Create a specific date and time using the of() method; 4. Use the plus/minus method to immutably increase and decrease the time; 5. Use ZonedDateTime and ZoneId to process the time zone; 6. Format and parse date strings through DateTimeFormatter; 7. Use Instant to be compatible with the old date types when necessary; date processing in modern Java should give priority to using java.timeAPI, which provides clear, immutable and linear

Comparing Java Frameworks: Spring Boot vs Quarkus vs Micronaut Comparing Java Frameworks: Spring Boot vs Quarkus vs Micronaut Aug 04, 2025 pm 12:48 PM

Pre-formanceTartuptimeMoryusage, Quarkusandmicronautleadduetocompile-Timeprocessingandgraalvsupport, Withquarkusoftenperforminglightbetterine ServerLess scenarios.2.Thyvelopecosyste,

How does garbage collection work in Java? How does garbage collection work in Java? Aug 02, 2025 pm 01:55 PM

Java's garbage collection (GC) is a mechanism that automatically manages memory, which reduces the risk of memory leakage by reclaiming unreachable objects. 1.GC judges the accessibility of the object from the root object (such as stack variables, active threads, static fields, etc.), and unreachable objects are marked as garbage. 2. Based on the mark-clearing algorithm, mark all reachable objects and clear unmarked objects. 3. Adopt a generational collection strategy: the new generation (Eden, S0, S1) frequently executes MinorGC; the elderly performs less but takes longer to perform MajorGC; Metaspace stores class metadata. 4. JVM provides a variety of GC devices: SerialGC is suitable for small applications; ParallelGC improves throughput; CMS reduces

Understanding Network Ports and Firewalls Understanding Network Ports and Firewalls Aug 01, 2025 am 06:40 AM

Networkportsandfirewallsworktogethertoenablecommunicationwhileensuringsecurity.1.Networkportsarevirtualendpointsnumbered0–65535,withwell-knownportslike80(HTTP),443(HTTPS),22(SSH),and25(SMTP)identifyingspecificservices.2.PortsoperateoverTCP(reliable,c

go by example defer statement explained go by example defer statement explained Aug 02, 2025 am 06:26 AM

defer is used to perform specified operations before the function returns, such as cleaning resources; parameters are evaluated immediately when defer, and the functions are executed in the order of last-in-first-out (LIFO); 1. Multiple defers are executed in reverse order of declarations; 2. Commonly used for secure cleaning such as file closing; 3. The named return value can be modified; 4. It will be executed even if panic occurs, suitable for recovery; 5. Avoid abuse of defer in loops to prevent resource leakage; correct use can improve code security and readability.

Java Concurrency Utilities: ExecutorService and Fork/Join Java Concurrency Utilities: ExecutorService and Fork/Join Aug 03, 2025 am 01:54 AM

ExecutorService is suitable for asynchronous execution of independent tasks, such as I/O operations or timing tasks, using thread pool to manage concurrency, submit Runnable or Callable tasks through submit, and obtain results with Future. Pay attention to the risk of unbounded queues and explicitly close the thread pool; 2. The Fork/Join framework is designed for split-and-governance CPU-intensive tasks, based on partitioning and controversy methods and work-stealing algorithms, and realizes recursive splitting of tasks through RecursiveTask or RecursiveAction, which is scheduled and executed by ForkJoinPool. It is suitable for large array summation and sorting scenarios. The split threshold should be set reasonably to avoid overhead; 3. Selection basis: Independent

See all articles