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

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++) {

  let count = 0;

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

    if (nums[j] < nums[i]) {

      count++;

    }

  }

  answer.push(count);

  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) => {

    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){

  const s = [...array], r = [];

  s.sort((a, b)=>{

    return a - b;

  });

  for(let n of array){

    r.push(s.indexOf(n));

  }

  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({

  length: datalength

}, () => getRandom(1, 100));

const mapper = arr => arr.map(i => arr.filter(n => n < i).length);

const sorter = nums => {

  const sorted = [...nums].sort();

  const result = nums.map((i) => {

    return sorted.findIndex(s => s === i);

  });

};

const iterator = arr => {

  const answer = [];

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

    let count = 0;

    for (let j = 0; j < arr.length; j++) {

      if (arr[j] < arr[i]) {

        count++;

      }

    }

    answer.push(count);

  }

  return answer;

};

const rankZero = array => {

  const s = [...array],

    r = [];

  s.sort((a, b) => {

    return a - b;

  });

  for (let n of array) {

    r.push(s.indexOf(n));

  }

  return r;

}

const reducer = arr => arr.map(v => arr.reduce((c, n) => c += (n < v), 0));

let fns = {

  'iterator': iterator,

  'mapper': mapper,

  'sorter': sorter,

  'reducer': reducer,

  'rankZero': rankZero

}

for (let [name, fn] of Object.entries(fns)) {

  let total = 0;

  for (i = 0; i < iterations; i++) {

    let t0 = performance.now();

    fn(data);

    let t1 = performance.now();

    total += t1 - t0;

  }

  console.log(name, (total / iterations).toFixed(2));

}