035-数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
这题并没有什么特别的技巧。它的一种解法和归并排序的思想非常相似，可以通过修改归并排序的代码得到。在每次merge的时候，由于前后两个子数组都已经排序好了，并且前面的子数组part1中的元素在原数组中的位置是比后面子数组part2中元素更前的，所以如果发现part1[i] > part2[j]，就可以确定，在part1中，至少有len(part1)-i个元素（part1[i:]）是比part2[j]大的。这些元素在原数组中，都排在part2[j]前面，因此原数组中的逆序数，至少有len(part1)-i。由于在merge中是序列比较part1和part2中元素的，所以可以在线性时间内求得因part1和part2产生的逆序对数量。答案的时间复杂度和归并排序的时间复杂度一样，只需要O(nlgn)。
其实在考虑归并排序之前，我先想到的是插入排序。使用一个新数组arr来保存排序结果。对原数组中的每个数data[i]，使用二分查找来查找在arr中的插入位置j。arr[j:]这些数在原数组中，都是处于data[i]前面，且大于它的。因此，data[i]会产生len(arr)-j个逆序对。这种做法甚至比归并排序更直观好懂，理论上的时间复杂度也是O(nlgn)。不过可能是因为频繁插入，这个解答超时了，我就根据评论区的提示转向归并排序……
class Solution:
def __init__(self):
self.count = 0
def merge_sort(self, data):
if len(data) <= 1:
return data
part1 = self.merge_sort(data[:len(data)//2])
part2 = self.merge_sort(data[len(data)//2:])
return self.merge(part1, part2)
def merge(self, part1, part2):
i, j = 0, 0
rtn = []
while i < len(part1) and j < len(part2):
if part1[i] > part2[j]:
rtn.append(part2[j])
j += 1
self.count += len(part1) - i
else:
rtn.append(part1[i])
i += 1
rtn.extend(part1[i:])
rtn.extend(part2[j:])
self.count %= 1000000007
return rtn
def InversePairs(self, data):
self.count = 0
self.merge_sort(data)
return self.count % 1000000007
class Solution {
long count;
void merge_sort(vector<int> &arr, int start, int end) {
if (end - start <= 1) return;
int mid = (start + end) / 2;
merge_sort(arr, start, mid);
merge_sort(arr, mid, end);
// merge
int i = start, j = mid, k = 0;
int tmp[end-start];
while (i < mid && j < end) {
if (arr[i] > arr[j]) {
tmp[k++] = arr[j++];
count += mid - i;
} else {
tmp[k++] = arr[i++];
}
}
while (i < mid) tmp[k++] = arr[i++];
while (j < end) tmp[k++] = arr[j++];
copy(tmp, tmp + (end - start), arr.begin() + start);
count %= 1000000007;
}
public:
int InversePairs(vector<int> data) {
count = 0;
merge_sort(data, 0, data.size());
return count;
}
};
029-最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
这题之前做过了，在数据结构这里面。不过我当时用了Python的heapq库，这次可以试试手写一个堆排序。
class Solution:
def heap(self, arr):
for i in range(len(arr)//2-1, -1, -1):
self.heapify(arr, i, len(arr))
def heapify(self, arr, i, length):
root = i
while root < length // 2:
min_idx = root
left, right = root * 2 + 1, root * 2 + 2
if arr[min_idx] > arr[left]:
min_idx = left
if right < length and arr[min_idx] > arr[right]:
min_idx = right
if min_idx != root:
arr[root], arr[min_idx] = arr[min_idx], arr[root]
root = min_idx
else:
break
def GetLeastNumbers_Solution(self, tinput, k):
if k > len(tinput):
return []
self.heap(tinput)
rtn = []
for i in range(k):
rtn.append(tinput[0])
tinput[0], tinput[-i-1] = tinput[-i-1], tinput[0]
self.heapify(tinput, 0, len(tinput)-i-1)
return rtn
class Solution {
void heapify(vector<int> &arr, int root, int len) {
int left, right, min_idx, tmp;
while (root < len / 2) {
left = root * 2 + 1, right = root * 2 + 2;
min_idx = root;
if (arr[min_idx] > arr[left]) min_idx = left;
if (right < len && arr[min_idx] > arr[right]) min_idx = right;
if (min_idx != root) {
tmp = arr[min_idx], arr[min_idx] = arr[root], arr[root] = tmp;
root = min_idx;
}
else break;
}
}
void heap(vector<int> &arr) {
for (int i = arr.size() / 2 - 1; i >= 0; --i)
heapify(arr, i, arr.size());
}
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if (k > input.size()) return {};
heap(input);
vector<int> rtn;
for (int i = 0, tmp; i < k; ++i) {
rtn.push_back(input[0]);
tmp = input[0], input[0] = input[input.size() - i - 1];
input[input.size() - i - 1] = tmp;
heapify(input, 0, input.size()-i-1);
}
return rtn;
}
};