河北省住房建设厅网站,个人免费网站注册,佛山网站建设怎么选择,做网站租什么服务器文章目录1 题目理解2 暴力解法3 分治法1 题目理解
输入#xff1a;int[] nums 输出#xff1a;计数的数组int[] counts 规则#xff1a;counts[i]表示nums中下标大于i#xff0c;值小于nums[i]的个数 Example 1: Input: nums [5,2,6,1] Output: [2,1,1,0] Explanation: T…
文章目录1 题目理解2 暴力解法3 分治法1 题目理解
输入int[] nums 输出计数的数组int[] counts 规则counts[i]表示nums中下标大于i值小于nums[i]的个数 Example 1: Input: nums [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
2 暴力解法
对于处理每个元素nums[i]依次数一数从i1到n小于nums[i]的数有多少个。
class Solution {public ListInteger countSmaller(int[] nums) {ListInteger list new ArrayListInteger();for(int i0;inums.length;i){int c 0;for(int ji1;jnums.length;j){if(nums[j]nums[i]){c;}}list.add(c);}return list;}
}时间复杂度O(n2)O(n^2)O(n2)
3 分治法
以下内容来自力扣官网。 数一数在右侧比自己小的元素个数这实际上就是在求逆序对。在学习算法过程中遇到过利用归并排序计算逆序对个数。
我们还是要在「归并排序」的「并」中做文章。我们通过一个实例来看看。假设我们有两个已排序的序列等待合并分别是 L { 8, 12, 16, 22, 100 } 和 R { 7, 26, 55, 64, 91 }。一开始我们用指针 lPtr 0 指向 L 的头部rPtr 0 指向 R 的头部。记已经合并好的部分为 M。 我们发现 lPtr 指向的元素大于 rPtr 指向的元素于是把 rPtr 指向的元素放入答案并把 rPtr 后移一位。 接着我们继续合并 此时 lPtr 比 rPtr 小把 lPtr 对应的数加入答案。如果我们要统计 8 的右边比 8 小的元素这里 7 对它做了一次贡献。如果待合并的序列 L { 8, 12, 16, 22, 100 }R { 7, 7, 7, 26, 55, 64, 91}那么一定有一个时刻lPtr 和 rPtr 分别指向这些对应的位置 下一步我们就是把 8 加入 M 中此时三个 7 对 8 的右边比 8 小的元素的贡献为 3。以此类推我们可以一边合并一边计算 R 的头部到 rPtr 前一个数字对当前 lPtr 指向的数字的贡献。
我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候只在 lPtr 右移的时候计算是基于这样的事实当前 lPtr 指向的数字比 rPtr 小但是比 R 中 [0 … rPtr - 1] 的其他数字大[0 … rPtr - 1] 的数字是在 lPtr 右边但是比 lPtr 对应数小的数字贡献为这些数字的个数。
但是我们又遇到了新的问题在「并」的过程中 88 的位置一直在发生改变我们应该把计算的贡献保存到哪里呢这个时候我们引入一个新的数组来记录每个数字对应的原数组中的下标例如 排序的时候原数组和这个下标数组同时变化则排序后我们得到这样的两个数组 我们用一个数组 ans 来记录贡献。我们对某个元素计算贡献的时候如果它对应的下标为 p我们只需要在 ans[p] 上加上贡献即可。
class Solution {private int[] index;private int[] temp;private int[] tempIndex;private int[] ans;private MapInteger,Integer valueIndexMap;public ListInteger countSmaller(int[] nums) {this.index new int[nums.length];this.temp new int[nums.length];this.tempIndex new int[nums.length];this.ans new int[nums.length];valueIndexMap new HashMapInteger,Integer();for(int i0;inums.length;i){valueIndexMap.put(nums[i],i);}for (int i 0; i nums.length; i) {index[i] i;}int l 0, r nums.length - 1;mergeSort(nums, l, r);ListInteger list new ArrayListInteger();for (int num : ans) {list.add(num);}return list;}public void mergeSort(int[] a, int l, int r) {if (l r) {return;}int mid (l r) 1;mergeSort(a, l, mid);mergeSort(a, mid 1, r);merge(a, l, mid, r);}public void merge(int[] a, int l, int mid, int r) {int i l, j mid 1, p l;while (i mid j r) {if (a[i] a[j]) {temp[p] a[i];tempIndex[p] index[i];ans[valueIndexMap.get(a[i])] (j - mid - 1);i;p;} else {temp[p] a[j];tempIndex[p] index[j];j;p;}}while (i mid) {temp[p] a[i];tempIndex[p] index[i];ans[valueIndexMap.get(a[i])] (j - mid - 1);i;p;}while (j r) {temp[p] a[j];tempIndex[p] index[j];j;p;}for (int k l; k r; k) {index[k] tempIndex[k];a[k] temp[k];}}
}时间复杂度O(nlogn)O(nlogn)O(nlogn)
