Application of merge sort in java interview-JavaInterview questions-php.cn

Application of merge sort in java interview

王林

Release： 2020-11-18 15:41:48

forward

2251 people have browsed it

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;
       }
       
   }
}

Copy after login

public  class solution{
 
  //一维数组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;
       }
       
   }
    
}

Copy after login

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);
		} 
	}
}

Copy after login

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!