- # -*- coding:utf-8 -*-
- class Solution:
- def __init__(self):
- self.cnt = 0
- self.tmp = []
- def InversePairs(self, data):
- n = len(data)
- self.tmp =[0] * n
- self.mergeSort(data,0,n-1)
- return self.cnt % 1000000007
- def mergeSort(self,nums,l,h):
- if h - l <1:
- return
- m = l + (h - l) // 2
- self.mergeSort(nums,l,m)
- self.mergeSort(nums,m+1,h)
- self.merge(nums,l,m,h)
- def merge(self,nums,l,m,h):
- i,j,k = l,m+1,l
- while i <= m or j <= h:
- if i> m:
- self.tmp[k] = nums[j]
- j += 1
- elif j> h:
- self.tmp[k] = nums[i]
- i += 1
- elif nums[i] <= nums[j]:
- self.tmp[k] = nums[i]
- i += 1
- else:
- self.tmp[k] = nums[j]
- j += 1
- self.cnt += m - i + 1
- k += 1
- k = l
- while k <= h:
- nums[k] = self.tmp[k]
- k += 1
- # write code here
本题超时, 据说是 oj 对 python 的判断有问题.
下面是参考的 java 实现可以提交:
- public class Solution {
- private long cnt = 0;
- private int[] tmp; // 在这里声明辅助数组, 而不是在 merge() 递归函数中声明
- public int InversePairs(int[] nums) {
- tmp = new int[nums.length];
- mergeSort(nums, 0, nums.length - 1);
- return (int) (cnt % 1000000007);
- }
- private void mergeSort(int[] nums, int l, int h) {
- if (h - l <1)
- return;
- int m = l + (h - l) / 2;
- mergeSort(nums, l, m);
- mergeSort(nums, m + 1, h);
- merge(nums, l, m, h);
- }
- private void merge(int[] nums, int l, int m, int h) {
- int i = l, j = m + 1, k = l;
- while (i <= m || j <= h) {
- if (i> m)
- tmp[k] = nums[j++];
- else if (j> h)
- tmp[k] = nums[i++];
- else if (nums[i] <= nums[j])
- tmp[k] = nums[i++];
- else {
- tmp[k] = nums[j++];
- this.cnt += m - i + 1; // nums[i]> nums[j], 说明 nums[i...mid] 都大于 nums[j]
- }
- k++;
- }
- for (k = l; k <= h; k++)
- nums[k] = tmp[k];
- }
- }
来源: http://www.bubuko.com/infodetail-3092057.html