专栏首页LeetCode<>并归排序&&小和问题&&逆序对问题
原创

<>并归排序&&小和问题&&逆序对问题

master公式的使用

T(N) = a*T(N/b) + O(N^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))

2) log(b,a) = d -> 复杂度为O(N^d * logN)

3) log(b,a) < d -> 复杂度为O(N^d)

master公式(也称主方法)是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法,(补充:分治策略的递归解法还有两个常用的方法叫做代入法和递归树法,以后有机会和亲们再唠),众所周知,分治策略中使用递归来求解问题分为三步走,分别为分解、解决和合并。

其中 a >= 1 and b > 1 是常量,其表示的意义是n表示问题的规模,a表示递归的次数也就是生成的子问题数,b表示每次递归是原来的1/b之一个规模,f(n)表示分解和合并所要花费的时间之和。

一.并归排序

思路,先把左边一半排序好,再把右边一部分排序好,最后将两部分合并起来就行了。merge的时候采用外排的方法,将排序好的放在一个临时的数组里面,然后在将这个临时数组的内容复制到原来的数组即可。

public void mergeSort(int[] arr,int left,int right){
    if (left >= right) return;
    int mid = left + ((right - left)>>1);
    mergeSort(arr,left,mid);
    mergeSort(arr,mid+1,right);
    merge(arr,left,mid,right);
}

public void merge(int [] array,int left,int mid,int right){
    int[] arr = new int[right - left +1];
    int i = left;
    int j = mid+1;
    int index = 0;
    while (i <= mid && j <= right){
        arr[index++] = array[i]<array[j]?array[i++]:array[j++];
    }
    while (i <= mid){
        arr[index++] = array[i++];
    }
    while (j <= right){
        arr[index++] = array[j++];
    }
    //复制数组
    for (int n = 0;n<arr.length;n++){
        array[n+left] = arr[n];
    }
}

二.小和问题

1.问题

在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和。 求一个数组

的小和。

例子:

[1,3,4,2,5]

1左边比1小的数, 没有;

3左边比3小的数, 1;

4左边比4小的数, 1、 3;

2左边比2小的数, 1;

5左边比5小的数, 1、 3、 4、 2;

所以小和为1+1+3+1+1+3+4+2=16

2.思路

1 3 4 2 5
划分为:1 3 4  | 2 5 
划分为:1 3 4  | 2 5 
划分为:1 3 | 4  | 2  | 5
划分为:1 | 3 | 4 | 2 | 5 

这个其实就是归并排序的过程,在每次比较之后,找到右边有多少个数大于左边的。

3.解法

public int smallSum(int [] array,int left ,int right){
    if (left == right){
        return 0;
    }
   int mid = left + (right - left)/2;
   return smallSum(array,left,mid) +
          smallSum(array,mid+1,right) +
          smallSumMerge(array,left,mid,right);
}

public int smallSumMerge(int [] array, int left ,int mid ,int right){
    int i = left;
    int j = mid+1;
    int [] help = new int[right - left +1];
    int index = 0;
    int result = 0;
    while (i <= mid && j <= right){
        result += array[i]<array[j] ? (right - j + 1)*array[i]:0;
        help[index++] = array[i]<array[j] ? array[i++] : array[j++];
    }

    while (i <= mid){
        help[index++] = array[i++];
    }

    while (j <= right){
        help[index++] = array[j++];
    }

    for (int n = 0 ; n < help.length ; n++){
        array[left+n] = help[n];
    }
    return result;
}

三.逆序对问题

ArrayList<Pair<Integer,Integer>> result = new ArrayList<>();
public void InversePairs(int [] array,int left ,int right){
    if (left == right){
        return ;
    }
    int mid = left + (right - left)/2;
    InversePairs(array,left,mid);
    InversePairs(array,mid+1,right);
    InversePairsMerge(array,left,mid,right);
}

public void InversePairsMerge(int [] array, int left ,int mid ,int right){
    int i = left;
    int j = mid+1;
    int [] help = new int[right - left +1];
    int index = 0;
    while (i <= mid && j <= right){
        if (array[i]>array[j]){
            for (int mm = i;mm<=mid;mm++){
                result.add(new Pair<>(array[mm],array[j]));
            }
        }
        help[index++] = array[i]<array[j] ? array[i++] : array[j++];
    }

    while (i <= mid){
        help[index++] = array[i++];
    }

    while (j <= right){
        help[index++] = array[j++];
    }

    for (int n = 0 ; n < help.length ; n++){
        array[left+n] = help[n];
    }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • <>快速排序&&荷兰国旗&&

    小于区域推着等于区域往右跑,但是等于区域与大于区域之间有一个待定的区域,所以array[cur]< num时候cur++,所以array[cur] > num...

    大学里的混子
  • 算法题目

    大学里的混子
  • 堆排序&&动态中位数

    heapify():  这里是指最大heapify。 我们只需要从  k = N / 2开始,  在k >= 1的条件下对 k 进行shiftDown(), 然...

    大学里的混子
  • [剑指offer][Java]调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位...

    后端技术漫谈
  • <>快速排序&&荷兰国旗&&

    小于区域推着等于区域往右跑,但是等于区域与大于区域之间有一个待定的区域,所以array[cur]< num时候cur++,所以array[cur] > num...

    大学里的混子
  • 数据结构与算法

    树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

    不作声
  • 一文搞定十大经典排序算法

    下面我们来逐一分析十大经典排序算法,主要围绕下列问题展开: 1、算法的基本思想是什么? 2、算法的代码实现? 3、算法的时间复杂度是多少?(平均、最好、最...

    matinal
  • 算法:贪心算法与二分查找-理论与实战

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    营琪
  • 影响Flink有状态函数和算子性能的3个重要因素

    本文重点介绍开发人员在有状态流处理应用中使用 Flink 的 Keyed State 的函数或算子评估性能时应牢记的3个重要因素。

    smartsi
  • [动态规划] 数字三角形问题(一维数组实现)

    一个数字三角宝塔。设数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。假设三角形行数小于等于100编程求解...

    孟君

扫码关注云+社区

领取腾讯云代金券