赞
踩
给定一个整数数组 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 个更小的元素
题解:
从每一个元素开始将其右侧小于它的元素个数记录下来然后填再对应的位置上
代码:
const countSmaller = (nums) => {
const counts = new Array(nums.length); //用额外空间保证原数组不被破坏
for (let i = 0; i < nums.length; i++) {
let count = 0;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
count++;
}
}
counts[i] = count;
}
return counts;
};
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。