剑指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题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

09-22 15:45
门头沟学院 Java
谁给娃offer我给...:我也遇到了,我说只要我通过面试我就去,实际上我根本就不会去😁
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务