在數組中計數反轉我正在設計一個算法來執行以下操作：給定的數組A[1... n]，為每一個i < j，找到所有的反轉對，這樣A[i] > A[j]..我使用合并排序和將數組A復制到數組B，然后比較這兩個數組，但我很難了解如何使用它來找到倒置的數量。如有任何提示或幫助，將不勝感激。
3 回答
LEATH
TA貢獻1936條經驗 獲得超7個贊
long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i+j] = right[j];
j++;
} else if (j == right.length) {
arr[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++;
} else {
arr[i+j] = right[j];
count += left.length-i;
j++;
}
}
return count;
}
long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return invCount(left) + invCount(right) + merge(arr, left, right);
}
飲歌長嘯
TA貢獻1951條經驗 獲得超3個贊
合并排序數組A并創建副本(數組B) 取A[1]，通過二進制搜索在排序數組B中找到其位置。這個元素的倒置數將比它在B中位置的索引數少一個，因為在A的第一個元素后面出現的每一個較低的數都是一個反轉。 2A.累積反轉的數目，以對抗變量num_inversion。 2B.將A[1]從數組A及其在數組B中的相應位置移除 從步驟2重新運行，直到A中沒有更多的元素。
POPMUISE
TA貢獻1765條經驗 獲得超5個贊
# O(n log n) def count_inversion(lst): return merge_count_inversion(lst)[1] def merge_count_inversion(lst): if len(lst) <= 1: return lst, 0 middle = int( len(lst) / 2 ) left, a = merge_count_inversion(lst[:middle]) right, b = merge_count_inversion(lst[middle:]) result, c = merge_count_split_inversion(left, right) return result, (a + b + c) def merge_count_split_inversion(left, right): result = [] count = 0 i, j = 0, 0 left_len = len(left) while i < left_len and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) count += left_len - i j += 1 result += left[i:] result += right[j:] return result, count #test code input_array_1 = [] #0 input_array_2 = [1] #0 input_array_3 = [1, 5] #0 input_array_4 = [4, 1] #1 input_array_5 = [4, 1, 2, 3, 9] #3 input_array_6 = [4, 1, 3, 2, 9, 5] #5 input_array_7 = [4, 1, 3, 2, 9, 1] #8 print count_inversion(input_array_1) print count_inversion(input_array_2) print count_inversion(input_array_3) print count_inversion(input_array_4) print count_inversion(input_array_5) print count_inversion(input_array_6) print count_inversion(input_array_7)
添加回答
舉報
0/150
提交
取消