JZ51 陣列中的逆序對
題目
在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列,求出這個陣列中的逆序對的總數P，并將P對1000000007取模的結果輸出， 即輸出P mod 1000000007
方法1：暴力
思路
演算法實作
兩個for回圈，如果前面的數大于后面的計數加1即可
問題
當輸入數過大時，需要的時間會很長，所以此方法不行
代碼
package mid.JZ51陣列中的逆序對;
import java.util.ArrayList;
public class Solution {
public int InversePairs1(int[] array) {
int k = 1000000007;
if (array.length <= 1) return 0;
int res = 0;
for (int i = 1; i < array.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (array[i] < array[j])
res++;
}
}
return res % k;
}
}
方法2 歸并排序思想
思路
- 先分：分呢，就是將陣列分為兩個子陣列，兩個子陣列分為四個子陣列，依次向下分，直到陣列不能再分為止！
- 后并：并呢，就是從最小的陣列按照順序合并，從小到大或從大到小，依次向上合并，最后得到合并完的順序陣列！
- 歸并統計法，關鍵點在于合并環節，在合并陣列的時候，當發現右邊的小于左邊的時候，此時可以直接求出當前產生的逆序對的個數，
代碼
package mid.JZ51陣列中的逆序對;
import java.util.Arrays;
public class Solution {
/**
* 分治
*
* @param array
* @return
*/
public int count = 0;
public int InversePairs(int[] array) {
divMerge(array, 0, array.length-1);
return count;
}
public void divMerge(int[] array, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
//分左邊
divMerge(array, left, mid);
//分右邊
divMerge(array, mid + 1, right);
//合并
int i = left;
int j = mid + 1;
//臨時陣列
int[] tmp = new int[right - left + 1];
int k = 0;
while (i <= mid && j <= right) {
if (array[i] > array[j]) {
tmp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
} else {
tmp[k++] = array[i++];
}
}
while (i <= mid) {
// 如果右邊的走完了 就把左邊的放到tmp后面
tmp[k++] = array[i++];
}
while (j <= right) {
// 如果左邊的走完了 就把右邊的放到tmp后面
tmp[k++] = array[j++];
}
// 把排好序的tmp 移到 array中
for(int l=0; l<k; l++) {
array[left++] = tmp[l];
}
}
public static void main(String[] args) {
System.out.println(new Solution().InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0}));
}
/**
* 暴力
*
* @param array
* @return
*/
public int InversePairs1(int[] array) {
int k = 1000000007;
if (array.length <= 1) return 0;
int res = 0;
for (int i = 1; i < array.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (array[i] < array[j])
res++;
}
}
return res % k;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540508.html
標籤：其他
上一篇：注解