给定一个长度为 n 的数组 nums ，请你返回一个新数组 count ，其中 count[i] 是 nums[i] 右侧小于 nums[i] 的元素个数。
数据范围： 
，数组元素值满足 
[编程题]右侧更小数
# -*- coding: utf-8 -*- import bisect # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: """ 题目： https://www.nowcoder.com/practice/b47363e689bc4a8088a68631d0c2754d?tpId=196&tqId=40450&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 借鉴： 大神：江南蜡笔小新 算法： 题目要求统计每一个nums[i]右侧小于nums[i]的元素的个数，因此我们采取逆序遍历nums，这里我们使用单调递增栈stack，维护逆序遍历序列 具体流程： 逆序遍历nums，对于nums[i]： stack中二分查找插入位置idx，更新count[i] = idx，再将nums[i]插入stack的下标idx位置 注意： 这里要使用list().insert方法，如果使用插入排序，会超时，如下所示，就超时了 # stack.append(nums[i]) # j = len(stack) - 1 # while j > 0 and stack[j] < stack[j - 1]: # 插入排序效率太低 # stack[j], stack[j - 1] = stack[j - 1], stack[j] # j -= 1 复杂度： 时间复杂度：O(nlogn), nlogn为n次二分查找的复杂度 空间复杂度：O(n)，辅助空间stack """ def smallerCount(self, nums): # write code here n = len(nums) count, stack = [0] * n, [] for i in range(n - 1, -1, -1): idx = bisect.bisect_left(stack, nums[i]) count[i] = idx stack.insert(idx, nums[i]) return count if __name__ == "__main__": sol = Solution() nums = [9, 8, 7, 6, 5] # nums = [5, 7, 8, 9, 6] res = sol.smallerCount(nums) print res
发表于 2022-06-23 17:15:20
回复(0)
import java.util.*;
/**
* NC360 右侧更小数
* @author d3y1
*/
public class Solution {
// 树状数组t
private int[] t;
// 线段树
private int[] segmentTree;
private SegNode[] segTree;
// 离散化: 将nums离散化(去重+排序), 转化为数组d
private int[] d;
// 归并
private int[] idx;
private int n;
private int[] result;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 相同 -> 315 计算右侧小于当前元素的个数 [leetcode]
* 相似 -> NC349 计算数组的小和 [nowcoder]
*
* 注意: 线段树lazy(懒惰标记)适用于区间修改(改善区间修改效率) -> https://oi-wiki.org/ds/seg/#线段树的区间修改与懒惰标记
*
* @param nums int整型ArrayList
* @return int整型ArrayList
*/
public ArrayList<Integer> smallerCount (ArrayList<Integer> nums) {
// return solution1(nums);
// return solution2(nums);
// return solution3(nums);
// return solution4(nums);
// return solution44(nums);
// return solution444(nums);
// return solution4444(nums);
// return solution5(nums);
return solution55(nums);
}
/**
* 二分
* @param nums
* @return
*/
private ArrayList<Integer> solution1(ArrayList<Integer> nums){
int n = nums.size();
result = new int[n];
ArrayList<Integer> list = new ArrayList<>();
list.add(nums.get(n-1));
// pos: 当前num(target)插入list位置(索引)
int left,right,mid,last,target,pos,sum;
for(int i=n-2; i>=0; i--){
last = list.get(n-i-2);
target = nums.get(i);
// 直接附加
if(last < target){
pos = n-i-1;
list.add(pos, target);
}
// 二分查找
else{
left = 0;
right = n-i-2;
while(left <= right){
mid = (left+right)>>1;
if(list.get(mid) < target){
left = mid+1;
}else{
right = mid-1;
}
}
pos = left;
list.add(pos, target);
}
result[i] = pos;
}
ArrayList<Integer> arrayList = new ArrayList<>();
for(int cnt : result){
arrayList.add(cnt);
}
return arrayList;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 树状数组(Binary Indexed Tree)(也称Fenwick树): 动态维护前缀和
*
* 参考: https://www.bilibili.com/video/BV1pE41197Qj/?vd_source=fa6990445a0e68c4b18e85e07647ab23
*
* @param nums
* @return
*/
private ArrayList<Integer> solution2(ArrayList<Integer> nums){
int n = nums.size();
result = new int[n];
// 离散化处理
discrete(nums);
// 初始化
init(n+1);
int num;
// 从后往前遍历
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// 树状数组id
int id = getIdByNum(num);
// 根据id获取前缀和 严格小于(id-1)
result[i] += query(id-1);
// 更新前缀和
update(id);
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 初始化
* @param length
*/
private void init(int length) {
t = new int[length];
Arrays.fill(t, 0);
}
/**
* 非负整数n在二进制表示下最低位1及后面的0所构成的数值
*
* 示例:
* lowBit(44) = lowBit(101100[2进制]) = 100[2进制] = 4[10进制]
*
* n 101100
* 取反: ~n 010011
* 取反+1: ~n+1 010100
*
* ~n+1 = -n (计算机存储使用补码, 取反加1后的值即为负的这个数)
*
* lowBit(44) = n & (~n+1) = n & (-n)
*
* @param x
* @return
*/
private int lowBit(int x) {
return x & (-x);
}
/**
* 更新前缀和: 从当前节点往树根逐层更新父节点
* @param pos
*/
private void update(int pos) {
while (pos < t.length) {
// 新增1次
t[pos] += 1;
// 当前节点的父节点
pos += lowBit(pos);
}
}
/**
* 查询前缀和: 从当前节点往左上逐个累加节点值
* @param pos
* @return
*/
private long query(int pos) {
long ret = 0;
while (pos > 0) {
ret += t[pos];
// 当前节点的左上节点
pos -= lowBit(pos);
}
return ret;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 排序: 归并
* @param nums
* @return
*/
private ArrayList<Integer> solution3(ArrayList<Integer> nums){
int n = nums.size();
Integer[] numsArr = new Integer[n];
nums.toArray(numsArr);
result = new int[n];
idx = new int[n];
for(int i=0; i<n; i++){
idx[i] = i;
}
mergeSort(numsArr, 0, n-1);
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 归并排序
* @param nums
* @param left
* @param right
* @return
*/
private void mergeSort(Integer[] nums, int left, int right) {
if(left >= right) {
return;
}
int mid = left+((right-left)>>1);
mergeSort(nums, left, mid);
mergeSort(nums, mid+1, right);
merge(nums, left, mid, right);
}
/**
* 合并
* @param nums
* @param left
* @param mid
* @param right
* @return
*/
private void merge(Integer[] nums, int left, int mid, int right) {
int len = right-left+1;
int[] helpIdx = new int[len];
int[] helpNum = new int[len];
int i = 0;
int p = left;
int q = mid+1;
while(p<=mid && q<=right) {
if(nums[p] <= nums[q]){
result[idx[p]] += q-mid-1;
helpIdx[i] = idx[p];
helpNum[i] = nums[p];
i++;
p++;
}else{
helpIdx[i] = idx[q];
helpNum[i] = nums[q];
i++;
q++;
}
}
while(p <= mid){
result[idx[p]] += q-mid-1;
helpIdx[i] = idx[p];
helpNum[i] = nums[p];
i++;
p++;
}
while(q <= right){
helpIdx[i] = idx[q];
helpNum[i] = nums[q];
i++;
q++;
}
for(i=0; i<len; i++){
idx[left+i] = helpIdx[i];
nums[left+i] = helpNum[i];
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
// /**
// * 线段树(Segment Tree): 数组实现(堆式存储)
// * @param nums
// * @return
// */
// private ArrayList<Integer> solution4(ArrayList<Integer> nums){
// n = nums.size();
// result = new int[n];
// segmentTree = new int[n*4];
// // 离散化处理
// discrete(nums);
// int num;
// // 从后往前遍历
// for(int i=n-1; i>=0; i--){
// num = nums.get(i);
// // 线段树id
// int id = getIdByNum(num);
// // 根据id获取区间和 严格小于(id-1) range: left<=right
// result[i] += sumRange(0, id-1);
// // 更新前缀和
// update(id, 1);
// }
// ArrayList<Integer> list = new ArrayList<Integer>();
// for(int cnt : result){
// list.add(cnt);
// }
// return list;
// }
// /**
// * 更新: 根据id进行更新
// * @param id
// * @param val
// */
// public void update(int id, int val) {
// change(id, val, 0, 0, n);
// }
// /**
// * 区间和
// * @param left
// * @param right
// * @return
// */
// public int sumRange(int left, int right) {
// return range(left, right, 0, 0, n);
// }
// /**
// * 递归: 更新线段树
// * @param index
// * @param val
// * @param node
// * @param start
// * @param end
// */
// private void change(int index, int val, int node, int start, int end) {
// if(start == end){
// segmentTree[node] += val;
// return;
// }
// int mid = start+(end-start)/2;
// if(index <= mid){
// change(index, val, node*2+1, start, mid);
// }else{
// change(index, val, node*2+2, mid+1, end);
// }
// segmentTree[node] = segmentTree[node*2+1]+segmentTree[node*2+2];
// }
// /**
// * 递归: 区间和
// * @param left
// * @param right
// * @param node
// * @param start
// * @param end
// * @return
// */
// private int range(int left, int right, int node, int start, int end) {
// if(left==start && right==end){
// return segmentTree[node];
// }
// int mid = start+(end-start)/2;
// if(right <= mid){
// return range(left, right, node*2+1, start, mid);
// }else if(left > mid){
// return range(left, right, node*2+2, mid+1, end);
// }else{
// return range(left, mid, node*2+1, start, mid) + range(mid+1, right, node*2+2, mid+1, end);
// }
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 线段树(Segment Tree): 数组实现(堆式存储)
* @param nums
* @return
*/
private ArrayList<Integer> solution44(ArrayList<Integer> nums){
n = nums.size();
result = new int[n];
segmentTree = new int[n*4+1];
// 离散化处理
discrete(nums);
int num;
// 从后往前遍历
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// 线段树id
int id = getIdByNum(num);
// 根据id获取区间和 严格小于(id-1) range: left<=right
result[i] += rangeSum(0, id-1);
// 更新前缀和
modify(id, 1);
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 更新: 根据id进行更新(单点修改)
* @param id
* @param val
*/
public void modify(int id, int val) {
modify(id, id, val, 0, 0, n);
}
/**
* 递归: 更新线段树(区间修改)
* @param left
* @param right
* @param val
* @param root
* @param start
* @param end
*/
private void modify(int left, int right, int val, int root, int start, int end){
// [left, right]: 修改区间
// [start, end]: 当前节点区间
if(left<=start && end<=right){
segmentTree[root] += (end-start+1)*val;
return;
}
int mid = start+(end-start)/2;
if(left <= mid){
modify(left, right, val, root*2+1, start, mid);
}
if(right > mid){
modify(left, right, val, root*2+2, mid+1, end);
}
segmentTree[root] = segmentTree[root*2+1]+segmentTree[root*2+2];
}
/**
* 区间和(区间查询)
* @param left
* @param right
* @return
*/
public int rangeSum(int left, int right) {
return rangeSum(left, right, 0, 0, n);
}
/**
* 递归: 区间和
* @param left
* @param right
* @param root
* @param start
* @param end
* @return
*/
private int rangeSum(int left, int right, int root, int start, int end){
// [left, right]: 查询区间
// [start, end]: 当前节点区间
if(left<=start && end<=right){
return segmentTree[root];
}
int mid = start+(end-start)/2;
int sum = 0;
if(left <= mid){
sum += rangeSum(left, right, root*2+1, start, mid);
}
if(right > mid){
sum += rangeSum(left, right, root*2+2, mid+1, end);
}
return sum;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 线段树(Segment Tree): 数组实现(堆式存储)
* @param nums
* @return
*/
private ArrayList<Integer> solution444(ArrayList<Integer> nums){
n = nums.size();
result = new int[n];
segmentTree = new int[n*4+1];
// 离散化处理
discrete(nums);
int num;
// 从后往前遍历
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// 线段树id
int id = getIdByNum(num);
// 根据id获取区间和 严格小于(id-1) range: left<=right
result[i] += querySum(0, id-1);
// 更新前缀和
change(id, 1);
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 更新: 根据id进行更新(单点修改)
* @param id
* @param val
*/
public void change(int id, int val) {
change(id, id, val, 1, 0, n);
}
/**
* 递归: 更新线段树(区间修改)
* @param left
* @param right
* @param val
* @param root
* @param start
* @param end
*/
private void change(int left, int right, int val, int root, int start, int end){
// [left, right]: 修改区间
// [start, end]: 当前节点区间
if(left<=start && end<=right){
segmentTree[root] += (end-start+1)*val;
return;
}
int mid = start+(end-start)/2;
if(left <= mid){
change(left, right, val, root*2, start, mid);
}
if(right > mid){
change(left, right, val, root*2+1, mid+1, end);
}
segmentTree[root] = segmentTree[root*2]+segmentTree[root*2+1];
}
/**
* 区间和(区间查询)
* @param left
* @param right
* @return
*/
public int querySum(int left, int right) {
return querySum(left, right, 1, 0, n);
}
/**
* 递归: 区间和
* @param left
* @param right
* @param root
* @param start
* @param end
* @return
*/
private int querySum(int left, int right, int root, int start, int end){
// [left, right]: 查询区间
// [start, end]: 当前节点区间
if(left<=start && end<=right){
return segmentTree[root];
}
int mid = start+(end-start)/2;
int sum = 0;
if(left <= mid){
sum += querySum(left, right, root*2, start, mid);
}
if(right > mid){
sum += querySum(left, right, root*2+1, mid+1, end);
}
return sum;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 线段树(Segment Tree): 数组实现(堆式存储)
* @param nums
* @return
*/
private ArrayList<Integer> solution4444(ArrayList<Integer> nums){
n = nums.size();
result = new int[n];
segTree = new SegNode[n*4+1];
segTree[1] = new SegNode(0, n);
// 离散化处理
discrete(nums);
int num;
// 从后往前遍历
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// 线段树id
int id = getIdByNum(num);
// 根据id获取区间和 严格小于(id-1) range: left<=right
result[i] += getSum(0, id-1);
// 更新前缀和
alter(id, 1);
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 更新: 根据id进行更新(单点修改)
* @param id
* @param val
*/
public void alter(int id, int val) {
alter(id, id, val, 1);
}
/**
* 递归: 更新线段树(区间修改)
* @param left
* @param right
* @param val
* @param root
*/
private void alter(int left, int right, int val, int root){
// [left, right]: 修改区间
// [start, end]: 当前节点区间
if(left<=segTree[root].start && segTree[root].end<=right){
segTree[root].sum += (segTree[root].end-segTree[root].start+1)*val;
return;
}
int mid = segTree[root].start+(segTree[root].end-segTree[root].start)/2;
if(segTree[root*2] == null){
segTree[root*2] = new SegNode(segTree[root].start, mid);
}
if(segTree[root*2+1] == null){
segTree[root*2+1] = new SegNode(mid+1, segTree[root].end);
}
if(left <= mid){
alter(left, right, val, root*2);
}
if(right > mid){
alter(left, right, val, root*2+1);
}
segTree[root].sum = segTree[root*2].sum+segTree[root*2+1].sum;
}
/**
* 区间和(区间查询)
* @param left
* @param right
* @return
*/
public int getSum(int left, int right) {
return getSum(left, right, 1);
}
/**
* 递归: 区间和
* @param left
* @param right
* @param root
* @return
*/
private int getSum(int left, int right, int root){
// [left, right]: 查询区间
// [start, end]: 当前节点区间
if(left<=segTree[root].start && segTree[root].end<=right){
return segTree[root].sum;
}
int mid = segTree[root].start+(segTree[root].end-segTree[root].start)/2;
if(segTree[root*2] == null){
segTree[root*2] = new SegNode(segTree[root].start, mid);
}
if(segTree[root*2+1] == null){
segTree[root*2+1] = new SegNode(mid+1, segTree[root].end);
}
int sum = 0;
if(left <= mid){
sum += getSum(left, right, root*2);
}
if(right > mid){
sum += getSum(left, right, root*2+1);
}
return sum;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
// /**
// * 线段树(Segment Tree): 树实现
// * @param nums
// * @return
// */
// private ArrayList<Integer> solution5(ArrayList<Integer> nums){
// n = nums.size();
// result = new int[n];
// TreeNode root = new TreeNode(0, n);
// // 离散化处理
// discrete(nums);
// int num;
// // 从后往前遍历
// for(int i=n-1; i>=0; i--){
// num = nums.get(i);
// // 线段树id
// int id = getIdByNum(num);
// // 根据id获取区间和 严格小于(id-1) range: left<=right
// result[i] += sumRange(root, 0, id-1);
// // 更新前缀和
// update(root, id, 1);
// }
// ArrayList<Integer> list = new ArrayList<Integer>();
// for(int cnt : result){
// list.add(cnt);
// }
// return list;
// }
// /**
// * 更新: 根据id进行更新
// * @param root
// * @param id
// * @param val
// */
// public void update(TreeNode root, int id, int val) {
// change(root, id, val);
// }
// /**
// * 递归: 更新线段树
// * @param root
// * @param index
// * @param val
// */
// private void change(TreeNode root, int index, int val) {
// if(root.start == root.end){
// root.sum += val;
// return;
// }
// int mid = root.start+(root.end-root.start)/2;
// if(root.left == null){
// root.left = new TreeNode(root.start, mid);
// }
// if(root.right == null){
// root.right = new TreeNode(mid+1, root.end);
// }
// if(index <= mid){
// change(root.left, index, val);
// }else{
// change(root.right, index, val);
// }
// root.sum = root.left.sum+root.right.sum;
// }
// /**
// * 区间和
// * @param root
// * @param left
// * @param right
// * @return
// */
// public int sumRange(TreeNode root, int left, int right) {
// return range(root, left, right);
// }
// /**
// * 递归: 区间和
// * @param root
// * @param left
// * @param right
// * @return
// */
// private int range(TreeNode root, int left, int right) {
// if(root == null){
// return 0;
// }
// if(left==root.start && right==root.end){
// return root.sum;
// }
// int mid = root.start+(root.end-root.start)/2;
// if(root.left == null){
// root.left = new TreeNode(root.start, mid);
// }
// if(root.right == null){
// root.right = new TreeNode(mid+1, root.end);
// }
// if(right <= mid){
// return range(root.left, left, right);
// }else if(left > mid){
// return range(root.right, left, right);
// }else{
// return range(root.left, left, mid)+range(root.right, mid+1, right);
// }
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 线段树(Segment Tree): 树实现
* @param nums
* @return
*/
private ArrayList<Integer> solution55(ArrayList<Integer> nums){
n = nums.size();
result = new int[n];
TreeNode root = new TreeNode(0, n);
// 离散化处理
discrete(nums);
int num;
// 从后往前遍历
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// 线段树id
int id = getIdByNum(num);
// 根据id获取区间和 严格小于(id-1) range: left<=right
result[i] += rangeSum(root, 0, id-1);
// 更新前缀和
modify(root, id, 1);
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int cnt : result){
list.add(cnt);
}
return list;
}
/**
* 更新: 根据id进行更新(单点修改)
* @param root
* @param id
* @param val
*/
public void modify(TreeNode root, int id, int val) {
modify(root, id, id, val);
}
/**
* 递归: 更新线段树(区间修改)
* @param root
* @param left
* @param right
* @param val
*/
private void modify(TreeNode root, int left, int right, int val) {
if(left<=root.start && root.end<=right){
root.sum += (root.end-root.start+1)*val;
return;
}
int mid = root.start+(root.end-root.start)/2;
if(root.left == null){
root.left = new TreeNode(root.start, mid);
}
if(root.right == null){
root.right = new TreeNode(mid+1, root.end);
}
if(left <= mid){
modify(root.left, left, right, val);
}
if(right > mid){
modify(root.right, left, right, val);
}
root.sum = root.left.sum+root.right.sum;
}
/**
* 区间和(区间查询)
* @param root
* @param left
* @param right
* @return
*/
public int rangeSum(TreeNode root, int left, int right) {
if(root == null){
return 0;
}
if(left<=root.start && root.end<=right){
return root.sum;
}
int mid = root.start+(root.end-root.start)/2;
if(root.left == null){
root.left = new TreeNode(root.start, mid);
}
if(root.right == null){
root.right = new TreeNode(mid+1, root.end);
}
int sum = 0;
if(left <= mid){
sum += rangeSum(root.left, left, right);
}
if(right > mid){
sum += rangeSum(root.right, left, right);
}
return sum;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* 离散化处理
*
* nums数组中可能有负数或者可能稀疏 -> 离散化处理
*
* @param nums
*/
private void discrete(ArrayList<Integer> nums) {
Set<Integer> set = new HashSet<>(nums);
int size = set.size();
d = new int[size];
int index = 0;
for(int num : set){
d[index++] = num;
}
Arrays.sort(d);
}
/**
* 二分: 根据num获取树状数组id (num -> id)
* @param num
* @return
*/
private int getIdByNum(int num) {
return Arrays.binarySearch(d, num)+1;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
public class TreeNode {
// 区间
int start,end;
int sum = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
private class SegNode {
private int start;
private int end;
private int sum = 0;
public SegNode(int start, int end){
this.start = start;
this.end = end;
}
}
}
发表于 2024-10-14 13:38:02
回复(0)
class Solution: def smallerCount(self , nums: List[int]) -> List[int]: # write code here def merge_sort(start, end): if end - start <= 1: return mid = (start + end) // 2 merge_sort(start, mid) merge_sort(mid, end) # Merge two sorted halves and count the smaller elements left_part = pairs[start:mid] right_part = pairs[mid:end] l, r = 0, 0 while start < end: if r >= len(right_part)&nbs***bsp;(l < len(left_part) and left_part[l][1] <= right_part[r][1]): pairs[start] = left_part[l] result[left_part[l][0]] += r l += 1 else: pairs[start] = right_part[r] r += 1 start += 1 if not nums: return [] # Pair each element with its index pairs = list(enumerate(nums)) result = [0] * len(nums) merge_sort(0, len(nums)) return result
发表于 2024-06-07 19:37:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型ArrayList
* @return int整型ArrayList
*/
public ArrayList<Integer> smallerCount(ArrayList<Integer> nums) {
int n = nums.size();
int[] count = new int[n];
int[] indices = new int[n];
// Initialize indices array
for (int i = 0; i < n; i++) {
indices[i] = i;
}
mergeSort(nums, indices, count, 0, n - 1);
ArrayList<Integer> result = new ArrayList<>();
for (int c : count) {
result.add(c);
}
return result;
}
private void mergeSort(ArrayList<Integer> nums, int[] indices, int[] count,
int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, indices, count, left, mid);
mergeSort(nums, indices, count, mid + 1, right);
merge(nums, indices, count, left, mid, right);
}
private void merge(ArrayList<Integer> nums, int[] indices, int[] count,
int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
int rightCount = 0;
while (i <= mid && j <= right) {
if (nums.get(indices[i]) <= nums.get(indices[j])) {
count[indices[i]] += rightCount;
temp[k++] = indices[i++];
} else {
rightCount++;
temp[k++] = indices[j++];
}
}
while (i <= mid) {
count[indices[i]] += rightCount;
temp[k++] = indices[i++];
}
while (j <= right) {
temp[k++] = indices[j++];
}
for (int p = 0; p < temp.length; p++) {
indices[left + p] = temp[p];
}
}
}
发表于 2024-05-21 13:40:24
回复(0)
想到用二叉树来解决，在数据平衡的情况下是时间复杂度是O(n*log2n)，空间复杂度是O(n)
import java.util.*;
public class Solution {
public ArrayList<Integer> smallerCount1(ArrayList<Integer> nums) {
// 最大最小取平均数
int min = nums.get(0);
int max = nums.get(0);
for (int num : nums) {
if (num < min) {
min = num;
} else if (num > max) {
max = num;
}
}
int mid = (min + max) >> 1;
// 设置根节点
TreeNode head = new TreeNode(mid);
head.count = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
// 从右向左遍历
int num = nums.get(i);
TreeNode par = head; // 每次从根节点出发
int count = 0; // 计算小于当前数num的值
while (true) {
if (num == par.val) {
// 当值相等，说明找到了，该节点计数+1
par.count = par.count + 1;
// count值加上当前节点的leftCount，leftCount每次添加节点的时候左滑计数，如果当前节点是父节点右孩子，代表： 父节点值 < num < 当前节点值
count = count + par.leftCount;
break;
} else if (num > par.val) {
// 向右滑
count = count + par.leftCount +
par.count; // 右滑结算当前节点的leftCount与当前节点的数量
TreeNode right = par.right;
if (right == null) {
// 右孩子为空说明到头了，初始化右孩子并且设置为count=1（构造设置）
right = new TreeNode(num);
par.right = right;
break;
}
// 右孩子不为空，右滑继续
par = right;
} else {
// 小于当前节点值，左滑并且leftCount+1
par.leftCount = par.leftCount + 1;
TreeNode left = par.left;
if (left == null) {
// 如果没左孩子，初始化左孩子，退出循环
left = new TreeNode(num);
par.left = left;
break;
}
// 左孩子不为空，继续循环向下
par = left;
}
}
// 设置结果
nums.set(i, count);
}
return nums;
}
private static class TreeNode {
private int val;
private int leftCount;
private int count;
private TreeNode left;
private TreeNode right;
public TreeNode(int val) {
this.val = val;
count = 1;
}
}
}
编辑于 2024-01-10 18:02:01
回复(1)
问题信息
难度：
5条回答
19收藏
3658浏览
通过挑战的用户
查看代码-
2022-09-13 14:29:57 -
2022-09-13 11:57:31
-
2022-09-11 20:42:23
-
2022-09-08 01:48:39 -
2022-09-03 10:08:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
