歸併排序(歸併排序求逆序對數)--16--歸併排序--Leetcode面試題51.數組中的逆序對

面試題51. 數組中的逆序對

 　　在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。

示例 1:

輸入: [7,5,6,4]
輸出: 5

限制：

0 <= 數組長度 <= 50000

 

歸併排序簡介：

　　　　歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

　　將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併(如下圖)。

　　歸併排序時間複雜度為NlogN,僅次於快速排序(點擊鏈接可看我之前發過的快排博文)，為穩定排序演算法，一般用於對總體無序，但是各子項相對有序的數列。

　　　　　　　　　　　　　　　　　　归并排序

歸併排序舉例：

　　　　如設有數列{6，202，100，301，38，8，1}

　　　　初始狀態：6,202,100,301,38,8，1

　　　　第一次歸併後：{6,202},{100,301},{8,38},{1}，比較次數：3；

　　　　第二次歸併後：{6,100,202,301}，{1,8,38}，比較次數：4；

　　　　第三次歸併後：{1,6,8,38,100,202,301},比較次數：4；

　　　　總的比較次數為：3+4+4=11；

　　　　逆序對數為14對；

歸併排序求逆序對數：具體思路是，在歸併的過程中計算每個小區間的逆序對數，進而計算出大區間的逆序對數（也可以用 樹狀數組來求解）

程式碼解析：

 1 class Solution {
15     //歸併排序：
16     int reversepairs = 0;//逆序對數
17     public int[] mergeSort(int[] nums, int left, int right){//歸併排序函數
18         if (left == right)//如果左邊界等於右邊界，說明數組只有一個值，不用排序
19             return new int[] { nums[left] };
20         int mid =  (right + left) / 2;//將數組分為兩半
21 
22         int[] leftArr = mergeSort(nums, left, mid); //左有序數組
23         int[] rightArr = mergeSort(nums, mid + 1, right); //右有序數組
24         int[] newNum = new int[leftArr.length + rightArr.length]; //新的有序數組
25 
26         int m = 0, i = 0, j = 0; 
27         //挨著挨著比較從左右兩邊的排好序的數組中從頭開始比較，誰小就先放誰進新的有序空數組
28         while (i < leftArr.length && j < rightArr.length){//直到左右兩個有序數組有一個的遍歷下標超出該數組的序列尾部
29             if(leftArr[i] <= rightArr[j])//左序列的元素小，就把左序列的該元素放入新的空的有序數組中
30                 newNum[m++] = leftArr[i++];
31             else{//右序列的元素小，就把右序列的該元素放入新的空的有序數組中
32                 newNum[m++] = rightArr[j++];
33                 reversepairs += leftArr.length - i;//左邊序列數組中還有leftArr.length-i個元素大於rightArr[j],所以這也是該區間的逆序對數35             }
36         }
37         while (i < leftArr.length)//如果左序列的元素還有剩餘的元素沒放進新的空數組中，就把左序列剩餘元素放入新的空的有序數組中
38             newNum[m++] = leftArr[i++];
39         while (j < rightArr.length)//如果右序列的元素還有剩餘的元素沒放進新的空數組中，就把右序列剩餘元素放入新的空的有序數組中
40             newNum[m++] = rightArr[j++];
41         return newNum;
42     }
43     public int reversePairs(int[] nums) {//入口函數
44         if(nums.length == 0)//如果給定的是個空數組，據題意返回0
45             return 0;
46         int[] newNums = mergeSort(nums, 0, nums.length - 1);//調用歸併排序函數，返回一個有序的數組
47         return reversepairs;//返回逆序對數
48     }
49 }

　　　　

Tags:

VirMach 便宜 VPS