TA貢獻1936條經(jīng)驗 獲得超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條經(jīng)驗 獲得超3個贊
TA貢獻1765條經(jīng)驗 獲得超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)
舉報