1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| def countSmaller(self, nums: List[int]) -> List[int]: l = len(nums) if l == 0: return [] if l == 1: return [0] tmp = [0 for _ in range(l)] counter = [0 for _ in range(l)] index = [i for i in range(l)] self.merge_sort(nums, tmp, 0, l - 1, counter, index)
return counter
def merge_sort(self, array, tmp, start, end, counter, index): if start == end: return mid = (start + end) // 2 self.merge_sort(array, tmp, start, mid, counter, index) self.merge_sort(array, tmp, mid + 1, end, counter, index) if array[index[mid]] > array[index[mid + 1]]: self.sortAndCount(array, tmp, start, mid, end, counter, index)
def sortAndCount(self, array, tmp, start, mid, end, counter, index): for i in range(start, end + 1): tmp[i] = index[i]
i = start j = mid + 1 for k in range(start, end + 1): if i > mid: index[k] = tmp[j] j += 1 elif j > end: index[k] = tmp[i] counter[index[k]] += end - mid i += 1 elif array[tmp[i]] <= array[tmp[j]]: index[k] = tmp[i] i += 1 counter[index[k]] += j - (mid + 1) else: index[k] = tmp[j] j += 1
|