常见算法题

发表于 更新于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 4 分钟

今天刷了几道常见算法题，这里简单MARK下。

数组去重

reduce

1
2
3
4
5
6
7
8
9
function uniqueArr(arr) {
       return arr.reduce((result, item) => {
         if (result.includes(item)) {
           return result;
         }
         result.push(item);
         return result;
       }, []);
     }

set特性

1
2
3
function uniqueArr(arr) {
      return Array.from(new Set(arr));
    }

for loop

1
2
3
4
5
6
7
8
9
function uniqueArr(arr) {
   const result = [];
   arr.forEach((item) => {
     if (!result.includes(item)) {
       result.push(item);
     }
   });
   return result;
 }

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
function bubbleSort(arr) {
      for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
          if (arr[j] < arr[j - 1]) {
            const temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
          }
        }
      }
      return arr;
    }

取1000个数字里面的质数|素数

注意

  • 如果一个数如果只能被 1 和它本身整除，这个数就是素数
  • 1不是素数

第一种办法的开销应该是最大的，每个数字需要计算2到n-1。

初级方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function isPrimeNumber(num) {
       if (num === 1 || num === 2) {
         return true;
       }
       for (let index = 2; index < num - 1; index++) {
         if (num % index === 0) {
           return false;
         }
       }
       return true;
     }

     function getPrimeNumbers(end) {
       const result = [];
       for (let index = 2; index <= end; index++) {
         isPrimeNumber(index) && result.push(index);
       }
       return result;
     }
     console.time('prime numbers - method #1');
     console.log(getPrimeNumbers(1000));
     console.timeEnd('prime numbers - method #1


试除法-改进版

注意，Math.sqrt开根号效率低于乘法。

1
2
3
4
5
6
7
8
9
10
11
12

 function isPrimeNumber(num) {
  if (num === 2) {
    return true;
  }
  for (let index = 2; index * index <= num; index++) {
    if (num % index === 0) {
      return false;
    }
  }
  return true;
}

正则法-思路巧妙-不建议使用

高耗内存，了解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isPrimeNumber3(index) {
       return !Boolean(
         Array(index)
           .fill(1)
           .join('')
           .match(/^1?$|^(11+?)\1+$/)
       );
     }

     function getPrimeNumbers3(end) {
       const result = [];
       for (let index = 2; index <= end; index++) {
         isPrimeNumber3(index) && result.push(index);
       }
       return result;
     }

sieve of Eratosthenes-埃式筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function getPrimeNumbers4(end) {
       const result = [];

       const defaultPrimes = Array(end + 1).fill(true);

       for (let i = 2; i < defaultPrimes.length; i++) {
         if (defaultPrimes[i]) {
           result.push(i);
           for (let j = i * 2; j < defaultPrimes.length; j += i) {
             defaultPrimes[j] = false;
           }
         }
       }

       return result;
     }

各个算法耗时

在线代码

我将该算法托管在了codesandbox，点击即可查看

写在最后

之前一直没有重视算法，痛定思痛，决定刻意练习下。实际上算法无处不在，只是一部分被各种类库，工具折叠了，另一部分是因为认识不够，很多实现方案避开了而已，所以代价就是程序的开销变大。因此，加强基本功，走起。

参考文档