《剑指offer》——数组中的逆序对

时间：2022-09-03 10:31:55

T:

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

  • 暴力搜索法

直接看代码，简洁明了。
code:

public int InversePairs(int [] array) {
    int nums = 0;

    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < i; j++) {
            if (array[j] > array[i]) {
                nums ++;
            }
        }
    }
    return nums;
}

如果只是单纯的从暴力搜索的角度去解决该问题，貌似简单了点儿，且这种情况下的耗时为 O(n2) 。我自己也没想出来用什么更简单高效的方法解决，之前有想到用动态规划思想，代码敲好后，突然发现思路有严重bug。。。

看到讨论版的代码，很多人说用归并排序，对于这个排序，我也忘得差不多了，重新学习！

  • more efficiency methods

先复习一下归并排序…
具体的算法思想不说了，给个链接：http://blog.csdn.net/morewindows/article/details/6678165/

《剑指offer》——数组中的逆序对

code:

    package niuke.sward2offer.inversePairs;

/**
 * 归并排序，递归方式
 * 
 * date: 2015.11.11 22:00
 * @author SSS
 *
 */
public class Solution1 {

/**
 * 将两个有序数组合并为一个新数组，耗时O(n)
 * 
 * @param array // 共用一个数组，即都在数组array上进行两个数组片段的重新排序
 * @param aStart
 * @param aEnd
 * @param bStart
 * @param bEnd
 * @param newArray
 */
public void merge(int []array, int aStart, int aEnd, int bStart, int bEnd, int []newArray) {
int i = aStart;
int j = bStart;

int count = 0;  // 新数组的下标
while (i <= aEnd && j <= bEnd) {
if (array[i] < array[j]) {
                    newArray[count ++] = array[i ++];
                }
else {
                    newArray[count ++] = array[j ++];
                }
            }

while (i <= aEnd) {
                newArray[count++] = array[i++];
            }
while (j <= bEnd) {
                newArray[count++] = array[j++];
            }

/**
 * 因为是要在下标为aStart和bEnd之间进行排序，所以将要有序的数列按对应下标覆盖array中原有的数据。
 */
for (int k = 0; k < bEnd - aStart + 1; k++) {
                array[aStart + k] = newArray[k];
            }

        }

/**
 * 归并排序的主体部分
 * @param array
 * @param start
 * @param end
 * @param newArray
 */
public void mergeSort(int []array, int start, int end, int []newArray) {
if (start < end) {
// 将下标为start和end这一部分的子数组从中间分为左、右两个部分
int mid = (start + end) / 2;
                mergeSort(array, start, mid, newArray); // 认为左边有序
                mergeSort(array, mid + 1, end, newArray);   // 认为右边有序
this.merge(array, start, mid, mid + 1, end, newArray);  
            }
        }

public static void main(String []args) {
int []array = {6, 3, 5, 9, 1, 8, 2, 7, 10, 4};
int []newArray = new int[array.length];

            Solution1 solution1 = new Solution1();
            solution1.mergeSort(array, 0, array.length - 1, newArray);

for (int i : newArray) {
                System.out.println(i);
            }
        }
    }

那么，能不能从这种方法的排序中得到点儿启发，从而算出原始数组中的逆序对呢？

归并排序的最底层，是从一个个的单个数字开始合并的，两个单个数字合并为一个二维有序数组，两个二维有序数组合并为一个有序的四维有序数组，……

归并排序的核心在于将两个有序数组合并为一个有序数组，代码如下：

    /**
 * 将两个有序数组合并为一个新数组，耗时O(n)
 * 
 * @param array // 共用一个数组，即都在数组array上进行两个数组片段的重新排序
 * @param aStart
 * @param aEnd
 * @param bStart
 * @param bEnd
 * @param newArray
 */
public void merge(int []array, int aStart, int aEnd, int bStart, int bEnd, int []newArray) {
int i = aStart;
int j = bStart;

int count = 0;  // 新数组的下标
while (i <= aEnd && j <= bEnd) {
if (array[i] < array[j]) {
                    newArray[count ++] = array[i ++];
                }
else {
                    newArray[count ++] = array[j ++];
                }
            }

while (i <= aEnd) {
                newArray[count++] = array[i++];
            }
while (j <= bEnd) {
                newArray[count++] = array[j++];
            }

/**
 * 因为是要在下标为aStart和bEnd之间进行排序，所以将要有序的数列按对应下标覆盖array中原有的数据。
 */
for (int k = 0; k < bEnd - aStart + 1; k++) {
                array[aStart + k] = newArray[k];
            }

        }

比如将两个有序数组: A=[a1,a2,a3,…]，B=[b1,b2,b3,…] 合并为一个有序数组 C=[b1,a1,a2,a3,b2,…] . 另外还一个潜在的条件，在原数组中，就是数组 A 中的元素都在 B 中元素的左边。

假设 a1>b1 ，那么 b1 要先放在数组 C 中，既然 a1>b1 ，且数组 A 也是有序数组，那么数组 A 中元素 a1 之后的元素（包括 a1 ）都要大于 b1 ，即都可以和 b1 组成逆序对，后面的依次类推。。。

所以，在归并排序的过程中求解逆序对的方法如下：设置一个全局变量，用于统计每次调用merge(…)函数时存在的逆序对。

code:

    package niuke.sward2offer.inversePairs;

/**
 * 在归并排序上的改进，可求得数组中的逆序对。
 * 
 * date:2015.11.11 22:40
 * @author SSS
 *
 */
public class Solution2 {

private int inversePairsCount = 0;

public int InversePairs(int [] array) {
int []newArray = new int[array.length];
this.mergeSort(array, 0, array.length - 1, newArray);

return inversePairsCount;
        }

/**
 * 将两个有序数组合并为一个新数组，耗时O(n)
 * 
 * @param array // 共用一个数组，即都在数组array上进行两个数组片段的重新排序
 * @param aStart
 * @param aEnd
 * @param bStart
 * @param bEnd
 * @param newArray
 */
public void merge(int []array, int aStart, int aEnd, int bStart, int bEnd, int []newArray) {
int i = aStart;
int j = bStart;

int count = 0;  // 新数组的下标
while (i <= aEnd && j <= bEnd) {
if (array[i] > array[j]) {
                    newArray[count ++] = array[j ++];
                    inversePairsCount += aEnd - i + 1;  // 将该轮合并当中出现的逆序对统计出来
                }
else {
                    newArray[count ++] = array[i ++];
                }
            }

while (i <= aEnd) {
                newArray[count++] = array[i++];
            }
while (j <= bEnd) {
                newArray[count++] = array[j++];
            }

/**
 * 因为是要在下标为aStart和bEnd之间进行排序，所以将要有序的数列按对应下标覆盖array中原有的数据。
 */
for (int k = 0; k < bEnd - aStart + 1; k++) {
                array[aStart + k] = newArray[k];
            }

        }

/**
 * 归并排序的主体部分
 * @param array
 * @param start
 * @param end
 * @param newArray
 */
public void mergeSort(int []array, int start, int end, int []newArray) {
if (start < end) {
// 将下标为start和end这一部分的子数组从中间分为左、右两个部分
int mid = (start + end) / 2;
                mergeSort(array, start, mid, newArray); // 认为左边有序
                mergeSort(array, mid + 1, end, newArray);   // 认为右边有序
this.merge(array, start, mid, mid + 1, end, newArray);  
            }
        }

public static void main(String []args) {
int []array = {5, 3, 4, 1};

            Solution2 solution2 = new Solution2();


            System.out.println("nums = " + solution2.InversePairs(array));
        }
    }
标签：

相关文章