我如何与数组中的其余元素进行比较

Question

我正在研究一个 leetcode 问题，我想不出一种方法来将数组中的其余元素相互比较。我计算出最大和最小的数字，但与其他数字进行比较是我遇到的麻烦。您将在下面找到问题和我的工作：

有多少数字小于当前数字？

给定数组 nums，对于每个 nums[i]，找出数组中有多少个数字小于它。也就是说，对于每个 nums[i]，您必须计算有效 j 的数量，使得 j != i 和 nums[j] < nums[i]。

返回数组中的答案。

示例 1：

Input: nums = [8,1,2,2,3]

Output: [4,0,1,1,3]

Explanation: 

For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 

For nums[1]=1 does not exist any smaller number than it.

For nums[2]=2 there exist one smaller number than it (1). 

For nums[3]=2 there exist one smaller number than it (1). 

For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

我的工作：

var smallerNumbersThanCurrent = (nums) => {

    const output = []

    const max = nums.reduce(function(a, b) {

        return Math.max(a, b);

    });

    const min = nums.reduce(function(a, b) {

        return Math.min(a, b);

    });

    for(let i = 0; i < nums.length; i++){

        if(nums[i] === max){

            output.push(nums.length - 1)

        } else if (nums[i] === min){

            output.push(0)

        }

        else if (nums[i] < max && nums[i] > min){

            //how do i compare with rest of the elements in the array?

        

        } 

       }

    }

Answer 1

使用嵌套循环。nums = [8,1,2,2,3];answer = [];for (let i = 0; i < nums.length; i++) {&nbsp; let count = 0;&nbsp; for (let j = 0; j < nums.length; j++) {&nbsp; &nbsp; if (nums[j] < nums[i]) {&nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; }&nbsp; }&nbsp; answer.push(count);&nbsp; console.log(`For nums[${i}]=${nums[i]} there are ${count} lower numbers`);}console.log(`Answer: ${answer}`);没有必要进行测试i != j，因为数字永远不会低于自身。

Answer 2

一种更简单的方法是简单地对数组进行排序，然后元素的索引会告诉你有多少比它少：const nums = [8,1,2,2,3]const sorted = [...nums].sort();const result = nums.map((i) => {&nbsp; &nbsp; return sorted.findIndex(s => s === i);});console.log(result);这样做的另一个好处是您不必为每个数字搜索整个数组。

Answer 3

一种方法是在值小于当前值的条件下过滤数组，然后统计过滤后的数组中值的个数：const nums = [8,1,2,2,3];const smallerNums = nums.map(v => nums.filter(n => n < v).length);console.log(smallerNums); // [4,0,1,1,3]或者，您可以在 reduce 中进行计数，这应该会快得多：const nums = [8, 1, 2, 2, 3];const smallerNums = nums.map(v => nums.reduce((c, n) => c += (n < v), 0));console.log(smallerNums); // [4,0,1,1,3]

Answer 4

我喜欢：function rankZero(array){&nbsp; const s = [...array], r = [];&nbsp; s.sort((a, b)=>{&nbsp; &nbsp; return a - b;&nbsp; });&nbsp; for(let n of array){&nbsp; &nbsp; r.push(s.indexOf(n));&nbsp; }&nbsp; return r;}console.log(rankZero([8, 1, 2, 2, 3]));

Answer 5

我对每个解决方案进行了性能测试。在我的电脑上（Intel Core I9-9900，64GB RAM）@StackSlave 的解决方案一直是最快的，其次是其他排序解决方案、reduce 解决方案、基本迭代和过滤器。您可以在下面自己运行测试：const datalength = 1000;const iterations = 100;const getRandom = (min, max) => Math.random() * (max - min) + min;const data = Array.from({&nbsp; length: datalength}, () => getRandom(1, 100));const mapper = arr => arr.map(i => arr.filter(n => n < i).length);const sorter = nums => {&nbsp; const sorted = [...nums].sort();&nbsp; const result = nums.map((i) => {&nbsp; &nbsp; return sorted.findIndex(s => s === i);&nbsp; });};const iterator = arr => {&nbsp; const answer = [];&nbsp; for (let i = 0; i < arr.length; i++) {&nbsp; &nbsp; let count = 0;&nbsp; &nbsp; for (let j = 0; j < arr.length; j++) {&nbsp; &nbsp; &nbsp; if (arr[j] < arr[i]) {&nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; answer.push(count);&nbsp; }&nbsp; return answer;};const rankZero = array => {&nbsp; const s = [...array],&nbsp; &nbsp; r = [];&nbsp; s.sort((a, b) => {&nbsp; &nbsp; return a - b;&nbsp; });&nbsp; for (let n of array) {&nbsp; &nbsp; r.push(s.indexOf(n));&nbsp; }&nbsp; return r;}const reducer = arr => arr.map(v => arr.reduce((c, n) => c += (n < v), 0));let fns = {&nbsp; 'iterator': iterator,&nbsp; 'mapper': mapper,&nbsp; 'sorter': sorter,&nbsp; 'reducer': reducer,&nbsp; 'rankZero': rankZero}for (let [name, fn] of Object.entries(fns)) {&nbsp; let total = 0;&nbsp; for (i = 0; i < iterations; i++) {&nbsp; &nbsp; let t0 = performance.now();&nbsp; &nbsp; fn(data);&nbsp; &nbsp; let t1 = performance.now();&nbsp; &nbsp; total += t1 - t0;&nbsp; }&nbsp; console.log(name, (total / iterations).toFixed(2));}