剑指offer-35-逆序对
数组中的逆序对
http://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
思路
- 排序算法
- 冒泡排序,每次交换,cnt++
- 归并排序,当[i,mid] [j,end],当i>j时,把j放入临时数组,这个时候,不仅i,j构成逆序,而且是[i,mid]与j都构成逆序对
cnt=(cnt+(mid-i+1))%1000000007,这里不能用cnt+=(mid-i+1)%1000000007
代码
非递归实现
public class Solution { int cnt=0; public int InversePairs(int [] array) { if (array.length <= 1) { return 0; } int len = 1; while (len < array.length) { int start = 0; while (start + 2 * len - 1 < array.length) { int mid = start + len - 1; int end = start + 2 * len - 1; merge(array, start, mid, end); start = start + 2 * len; } //剩余无法构成完整的两组也要进行处理 if (start + len - 1 < array.length) merge(array, start, start + len - 1, array.length - 1); len = len * 2; } return cnt; } public void merge(int[] arr, int start, int mid, int end) { int i = start; int j = mid + 1; int[] temp = new int[end - start + 1]; int index = 0; while (i <= mid && j <= end) { if (arr[i] <= arr[j]) temp[index++] = arr[i++]; else{ temp[index++] = arr[j++]; cnt =(cnt+(mid-i+1)) %1000000007; } } while (i <= mid) temp[index++] = arr[i++]; while (j <= end) temp[index++] = arr[j++]; for (int k = start; k <= end; k++) arr[k] = temp[k - start]; } }
剑指offer与数据结构 文章被收录于专栏
本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构