算法练习

问题定义 给定一个长度为n的整数数组，计算数组中的逆序对的数量并返回 逆序对的定义如下：对于数组的第i个和第j个元素，如果满足i<j且a[i]>a[j]，则其为一个逆序对；否则不是。 数据范围 1≤n≤100000，数组中的元素的取值范围 [1,1e9]。 示例：输入[2,3,4,5,6,1]，输出5 解释：逆序对共5对,[2, 1], [3, 1], [4, 1], [5, 1], [6, 1] 本题暴力硬解的复杂度为$O(n^2)$，较为繁琐，于是考虑是否存在复杂度为$O(nlogn)$的算法 要求逆序数，就不能在寻找数对时未经相关处理就更改数组元素顺序打乱原有顺序，因此要找到一种在实施过程中能够在一定程度上保留元素顺序关系的算法。 设想一种很理想的情况：元素a与b满足逆序数的定义（即a>b且i<j），同时还已知有一批比a大的数，那么很容易推知这一批数都可以与b构成逆序数，其个数就等于这批数的个数 以上情况正好符合归并排序的过程，首先在这里复习一下归并排序的原理： 归并排序 归并排序先递归地两两划分数组，每轮递归中都将整个数组分为左右两个部分，然后在每一次左右划分完成后，为左右两个数组各设置一个指针i与j，比较大小并将小者放入一个临时数组中（这个临时数组的长度是本轮划分左右数组的总长），放入一边的指针前进一步，再继续比较。当某一边全部比较完后，将可能还未放完的另一边数组元素全部放入临时数组 代码可以是： class Solution { public int[] mergeSort(int[] nums, int l, int r) { // l=r证明已经划分到单个元素，返回的排序数组就是以这个单元素组成的数组 if (l == r) return new int[]{nums[l]}; int mid = (l + r) / 2; int[] leftNums = mergeSort(nums, l, mid); int[] rightNums = mergeSort(nums, mid+1, r); // 能执行到这里，说明左右划分都已完成，此时如果左右都是单元素数组[2][3]，则这个栈会返回[2,3] // 此时如果左右都是多元素数组，那至少能保证这两个数组各自的内部是有序的 int[] tempNums = new int[leftNums.length + rightNums.length]; int i = 0, j = 0, m = 0; // i左j右，m是临时数组索引 while (i < leftNums.length && j < rightNums.length) tempNums[m++] = leftNums[i] < rightNums[j] ? leftNums[i++] : rightNums[j++]; // 接下来处理一边走完一边还没走完的情况，由于单边必定已经有序，所以直接顺序放入即可 while (i < leftNums.length) tempNums[m++] = leftNums[i++]; while (j < rightNums.length) tempNums[m++] = rightNums[j++]; return tempNums; } } 题解 回到本题，核心在于：在归并排序比较leftNums[i]与rightNums[j]的大小关系时，如果正好左大于右，（即满足逆序数的定义），则可以直接确定这两个数之间的数都满足逆序数的定义 ...

顺序统计的问题是： 给定一组元素，找到其中第k大（小）的元素 仅从功能实现上考虑，完全可以先对数组排序，然后直接取nums[k-1]作为结果输出。但这个方法是需要先对数组排序的，所以效率为$\Theta(nlogn)$，我们的目标是找到一种$\Theta(n)$的方法 基于随机数的分治法 为了尽量压缩时间，可以考虑能不能在排序进行时就顺便找到所需元素，为此，可以使用快速排序算法中的分治思想 在快速排序算法中，每选定一个基准数pivot，就需要将所有小于pivot的元素移动至其左侧、所有大于pivot的元素移动至其右侧，当全部移动完成时，左右指针会正好相遇在pivot元素上 不难想到，当获得了pivot的索引值index，就可以直接检查index是否正好等于k-1（假设k指第k小的元素值），如果相等，则说明这个pivot就是要找的第k小的元素；如果不等，则进一步检查index与k-1之间的大小关系并确定新pivot： 如果index > k-1，说明要寻找的元素相较于pivot来说更小，那么去小于pivot的区域再找 如果index < k-1，说明要寻找的元素相较于pivot来说更大，那么去大于pivot的区域再找 以上过程完全可以用递归来实现（事实上这也是快速排序所进行的过程），而在区域中选取pivot实际上是随机取得的。另外，当传入的左右限制left == right时，说明此区域仅有一个元素，需要寻找的只能是该元素，直接返回nums[left]即可 代码实现（Java） 类的总体结构应为： import java.util.Random; class Find { private int[] nums; private int k; public Find(int[] nums) {...} public int getKElement(int k) {...} private int randomSelect(int left, int right) {...} // 递归部分，选取随机数、划分后判断 private int partition(int random, int p, int q) {...} // 划分部分 private void swap(int i, int j) {...} // 用于交换数组元素的工具方法 } 先编写划分部分的方法，输入数组、随机索引值、左右限制，输出划分后pivot的索引值： public int partition(int random, int p, int q) { while (p != q) { int pivot = nums[random]; while (pivot > nums[p]) p++; swap(nums, p, random); random = p; while (pivot < nums[q]) q--; swap(nums, q, random); random = q; } return random; } 编写递归部分： ...