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{ //一维数组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!