乐趣区

关于leetcode:力扣之有多少小于当前数字的数字

jiezi

题目形容

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出无效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i]。

以数组模式返回答案。

示例 1：

输出：nums = [8,1,2,2,3]
输入：[4,0,1,1,3]
解释：对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。对于 nums[1]=1 不存在比它小的数字。对于 nums[2]=2 存在一个比它小的数字：（1）。对于 nums[3]=2 存在一个比它小的数字：（1）。对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输出：nums = [6,5,4,8]
输入：[2,1,0,3]

示例 3：

输出：nums = [7,7,7,7]
输入：[0,0,0,0]

力扣原题目地址：https://leetcode.cn/problems/…

思路解法

题目并不难，就是做大小的比拟并统计次数，遇到这样的题目，咱们首先相到的就是暴力循环破解的形式

双层循环比拟

第一层循环，取到以后的每一项，再套一层循环，顺次比拟其余项是否小于以后项，当然本身项不必比拟，间接跳过即可，如下代码：

var smallerNumbersThanCurrent = function (nums) {
    // 1. 创立一个和传进来的数组长度统一的数组，且每一项都是 0（为 0 是为了后续统计次数）let resultArr = (new Array(nums.length)).fill(0)
    for (let i = 0; i < nums.length; i++) { // 2. 外层遍历是为了拿到每一项与其余项作比拟
        let item = nums[i] // 3. 拿到当下项
        for (let j = 0; j < nums.length; j++) { // 4. 再循环一次是为了拿到别的项
            if (i == j) { // 5. 本身不必比拟大小
                // console.log('本身跳过不统计次数');
            } else {if (item > nums[j]) { // 6. 若不是本身项，能够比拟大小
                    resultArr[i] = resultArr[i] + 1 // 7. 应用初始创立的 0 进行次数统计
                }
            }
        }
    }
    return resultArr
};

双层循环比拟提交图

从小到大排序后的索引即为小于以后项的次数

假如数组为：[2,1,1,8]，排序后为：[1,1,2,8]，认真扫视咱们会发现，后果就是：[2,0,0,3]，正好就是排序后的索引（若有反复项只取第一项的索引为准），因为小于即会想到排序。代码如下：

 var smallerNumbersThanCurrent = function (nums) {
    // 拷贝一个新的数组，将原有的数组做从小到大排序
    let newSortNums = [...nums]
    newSortNums.sort((a, b) => {return a - b})
    // 原有数组的每一项在排序后数组的索引是多少
    let resultArr = nums.map((item) => {return newSortNums.indexOf(item)
    })
    return resultArr // 即为后果
};

从小到大排序后的索引即为小于以后项的次数提交图

确实效率会比双层 for 循环比拟好一些

知识点温习之 js 创立数组的形式

为什么要说这个呢？因为解法一中有这样的代码：let resultArr = (new Array(nums.length)).fill(0)

js 中创立数组个别有如下形式：

1. 间接创立，如：let arr = [111, 222, 3333, 444]

2. 构造函数创立，如创立一个空数组（长度也为空）：let arr = new Array()、创立一个空数组，长度为4，然而每一项的值都为空：let arr = new Array(4)

2.1 如果想要填充值，能够应用 fill 办法

fill(value,start,end)办法用于给数组填充数据，减少项。参数有必带参数 value，可选参数start 起始索引 和end 终止索引，会更改影响原数组，返回值批改后的数组

Array.prototype.fill() mdn: https://developer.mozilla.org…

new Array(count).fill(initValue)办法有时候很好用，因为有时候，须要创立 动态变化的长度的空数组或对立指定默认值 之类的。这样的话，须要多长的数组，count为 几即可，须要指定默认值，initValue填写即可

每天学习一点点，每天提高一点点。

这大略就是：老黄牛精力吧

退出移动版