常见算法题

今天刷了几道常见算法题,这里简单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

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
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,点击即可查看

写在最后

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

参考文档