计数排序

第一眼

function countingSort(arr: number[]): number[] {
  // Write your code here
  let len: number = arr.length;
  const newArr: number[] = new Array(len).fill(0);
  for (let i = 0; i < len; i++) {
    if (arr[i]) {
    }
  }
}

然后尬住了

拿到arr长度len

开辟长度为len的数组，并填充0

const newArr:number[] = new Array(len).fill(0)

第二眼

要求按arr最大值来定义数组长度，比如[1,1,3,2,1]的范围是[0…3],所以开辟res =[0,0,0,0]

所以得拿到最大值?

const max = arr.find(...)

find只能返回符合条件的第一个元素，不能找最大值

解构找到最大值

const max = Math.max(...arr);

reduce找到最大值

const max = arr.reduce((acc, item) => {
  return Math.max(acc, item);
}, arr[0]);

acc当前最大值,item遍历元素

当然，acc是reduce原本就是接收的4个参数之一,还有个可选的initialValue

1. Accumulator acc(累加器)
2. Current Value cur(当前值)
3. Current index idx(当前索引)
4. Source Array src(源数组)

遍历arr

如果出现值，在特定位置计数加1

arr[i] newArr[i] ++

第三眼

function countingSort(arr: number[]): number[] {
  // Write your code here
  let len: number = arr.length;
  const max = Math.max(...arr);
  const newArr = Array(max).fill(0);
  for (let i = 0; i < len; i++) {}
}

相同数值再出现,再相同位置+1

有错

并非const newArr = Array(max).fill(0)

而是const newArr = Array(max + 1).fill(0)

为什么？

因为要创建[0,max]全闭数组

第四眼

到底怎么计算元素出现次数?

for (let num of arr) {
  newArr[num]++;
}

• 通过遍历输入数组 arr 中的每个数字 num，我们给 countArr[num] 这个位置的值加 1。
• 例如，如果输入数组是[2, 3, 2, 1]，则newArr将变为[0, 1, 2, 1]
  • countArr[1] = 1 （数字 1 出现 1 次）
  • countArr[2] = 2 （数字 2 出现 2 次）
  • countArr[3] = 1 （数字 3 出现 1 次）

寄了

第五眼

看看洋人怎么写的

 const frequencyArray = (new Array(100)).fill(0);
    const length = arr.length;
    for (let i = 0; i < length; i++) {
        frequencyArray[arr[i]] += 1;
    }

    return frequencyArray;
}

frequencyArray[arr[i]] += 1;疑似有点天才了