HackerRank三个月挑战第二周

计数排序

第一眼
1
2
3
4
5
6
7
8
9
10
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]

所以得拿到最大值?

1
const max = arr.find(...)

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

解构找到最大值
1
const max = Math.max(...arr)
reduce找到最大值
1
2
3
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] ++

第三眼
1
2
3
4
5
6
7
8
9
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]全闭数组

第四眼

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

1
2
3
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 次）

寄了

第五眼

看看洋人怎么写的

1
2
3
4
5
6
7
8
 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;疑似有点天才了