難度：Hard
題目：
給你一個(gè)整數(shù)數(shù)組?
nums?，按要求返回一個(gè)新數(shù)組?counts?。數(shù)組?counts?有該性質(zhì)：?counts[i]?的值是?nums[i]?右側(cè)小于?nums[i]?的元素的數(shù)量。?
示例 1：
輸入：nums = [5,2,6,1]
輸出：[2,1,1,0]
解釋?zhuān)?/strong>
5 的右側(cè)有 2 個(gè)更小的元素 (2 和 1)
2 的右側(cè)僅有 1 個(gè)更小的元素 (1)
6 的右側(cè)有 1 個(gè)更小的元素 (1)
1 的右側(cè)有 0 個(gè)更小的元素
?示例 2：
輸入：nums = [-1] 輸出：[0]
?示例 3：
輸入：nums = [-1,-1] 輸出：[0,0]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
?Related Topics
- 樹(shù)狀數(shù)組
- 線(xiàn)段樹(shù)
- 數(shù)組
- 二分查找
- 分治
- 有序集合
- 歸并排序
重點(diǎn)！??！解題思路
明確解題思路：
? ? ? ? 題中要求求出右側(cè)小于當(dāng)前元素的數(shù)量，如果將數(shù)組拆分開(kāi)來(lái)，左右兩邊都是降序排列，如果當(dāng)左邊數(shù)組有一個(gè)值大于右邊數(shù)組的其中一個(gè)值，那么就意味著比當(dāng)前左邊這個(gè)數(shù)小的元素有右邊那個(gè)數(shù)到右邊數(shù)組末尾那么多個(gè)，即題目可使用歸并排序來(lái)解決。
源碼+講解：
class Solution {
class Data { //因?yàn)槟阋涗浢總€(gè)值所對(duì)應(yīng)得右邊元素個(gè)數(shù)，hashmap太麻煩，我們直接封裝一個(gè)內(nèi)部類(lèi)
int ind, val, cnt; //對(duì)應(yīng)下標(biāo)，值，右邊對(duì)應(yīng)得元素
public Data(int ind, int val) { //初始化
this.ind = ind;
this.val = val;
cnt = 0;
}
}
Data[] temp; //歸并排序的克隆數(shù)組
public List<Integer> countSmaller(int[] nums) {
temp = new Data[nums.length];
Data[] data = new Data[nums.length]; //待排序數(shù)組
for (int i = 0; i < nums.length; i++) { //將每個(gè)元素封裝到類(lèi)中
data[i] = new Data(i, nums[i]);
}
merge_sort(data, 0, data.length - 1); //開(kāi)始?xì)w并排序
Arrays.sort(data, new Comparator<Data>() { //當(dāng)歸并排序后，我們需要每個(gè)數(shù)組下標(biāo)從小到大來(lái)輸出，那么我們就需要一個(gè)小頂堆
@Override
public int compare(Data o1, Data o2) {
return o1.ind - o2.ind;
}
});
List<Integer> res = new ArrayList<>(); //集合結(jié)果用來(lái)還原堆中的值
for (Data datum : data) {
res.add(datum.cnt);
}
return res;
}
//很基礎(chǔ)的一個(gè)歸并排序解法 如果有不懂得朋友 可以看看我前面發(fā)的題
public void merge_sort(Data[] data, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(data, l, mid);
merge_sort(data, mid + 1, r);
int k = l, p1 = l, p2 = mid + 1;
while (p1 <= mid || p2 <= r) {
if (p2 > r || (p1 <= mid && data[p1].val > data[p2].val)) {
data[p1].cnt+=(r-p2+1);
temp[k++] = data[p1++];
} else {
temp[k++] = data[p2++];
}
}
for (int i=l;i<=r;i++) data[i]=temp[i];
}
}?運(yùn)行結(jié)果：
![LeetCode[315]計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù),算法刷題篇,快速排序,# 歸并排序(Merge-Sort):從二路到多路,leetcode,算法,排序算法](https://imgs.yssmx.com/Uploads/2023/07/610294-1.png)
如果您還有什么疑問(wèn)或解答有問(wèn)題，可在下方評(píng)論，我會(huì)及時(shí)回復(fù)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-610294.html
系列持續(xù)更新中，點(diǎn)個(gè)訂閱吧，喜歡練習(xí)算法那就點(diǎn)個(gè)攢吧?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-610294.html
到了這里，關(guān)于LeetCode[315]計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
