Java实现 LeetCode 315 计算右侧小于当前元素的个数
2023-09-14 08:58:05 时间
315. 计算右侧小于当前元素的个数
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
class Solution {
public static List<Integer> countSmaller(int[] nums) {
if (nums.length == 0) {
return new ArrayList<>();
}
int min = Integer.MAX_VALUE; // nums数组最小值
for (int value : nums) {
if (value < min) {
min = value;
}
}
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i] - min + 1;
}
int max = Integer.MIN_VALUE;
for (int value : nums) {
if (value > max) {
max = value;
}
}
int[] BITree = new int[max + 1];
BITree[0] = 0;
int[] countArr = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
int count = getSum(nums[i] - 1, BITree);
countArr[i] = count;
update(nums[i], BITree);
}
List<Integer> result = new ArrayList<>();
for (int value : countArr) {
result.add(value);
}
return result;
}
//获取和
public static int getSum(int value, int[] BITree) { // 获得a[i]从1,value的和
int sum = 0;
while (value > 0) {
sum += BITree[value];
value -= (value & -value);
}
return sum;
}
//单点更新值
public static void update(int value, int[] BITree) {
while (value <= BITree.length - 1) {
BITree[value] += 1;
value += (value & -value);
}
}
// public List<Integer> countSmaller(int[] nums) {
// ArrayList<Integer> list = new ArrayList<Integer>();
// int len = nums.length;
// Integer[] result = new Integer[len];
// for(int i = len-1;i>=0;i--) {
// //将每个数插入到list中//使用二分查找
// int start = 0; int end = list.size();
// while(start<end) {
// int middle = start+(end-start)/2;
// //判断中间的数
// if(list.get(middle) < nums[i]) {//严格小于的话,只能在后面部分,并且不包含middle
// start = middle+1;
// }else {
// end = middle;
// }
// }
// result[i] = start;
// list.add(start,nums[i]);
// }
// return Arrays.asList(result);
// }
}
相关文章
- Java实现 LeetCode 820 单词的压缩编码(暴力)
- Java实现 LeetCode 797 所有可能的路径 (DFS)
- Java实现 蓝桥杯 算法提高 高精度减法(JDK方法)
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 682 棒球比赛(暴力)
- Java实现 LeetCode 520 检测大写字母
- Java实现 LeetCode 519 随机翻转矩阵
- Java实现 LeetCode 388 文件的最长绝对路径
- Java实现 LeetCode 367 有效的完全平方数
- Java实现 LeetCode 357 计算各个位数不同的数字个数
- Java实现 LeetCode 315 计算右侧小于当前元素的个数
- Java实现 LeetCode 304 二维区域和检索 - 矩阵不可变
- Java实现 LeetCode 102 二叉树的层次遍历
- Java实现 蓝桥杯 基因牛的繁殖
- Java实现 LeetCode 16 最接近的三数之和
- Java实现 LeetCode 125 验证回文串
- Java实现 LeetCode 242 有效的字母异位词
- Java 是如何实现跨平台的?
- java实现第七届蓝桥杯机器人塔
- (Java实现) 删数问题
- 用Java打造高效可扩展的分布式数据流处理系统
- java中set和get方法的理解