常见算法题
·
2 min read
今天刷了几道常见算法题，这里简单MARK下。
数组去重
reduce
function uniqueArr(arr) {
return arr.reduce((result, item) => {
if (result.includes(item)) {
return result;
}
result.push(item);
return result;
}, []);
}
set特性
function uniqueArr(arr) {
return Array.from(new Set(arr));
}
for loop
function uniqueArr(arr) {
const result = [];
arr.forEach((item) => {
if (!result.includes(item)) {
result.push(item);
}
});
return result;
}
冒泡排序
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。
初级方法
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开根号效率低于乘法。
function isPrimeNumber(num) {
if (num === 2) {
return true;
}
for (let index = 2; index * index <= num; index++) {
if (num % index === 0) {
return false;
}
}
return true;
}
正则法-思路巧妙-不建议使用
高耗内存，了解即可。
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-埃式筛法
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，点击即可查看
写在最后
之前一直没有重视算法，痛定思痛，决定刻意练习下。实际上算法无处不在，只是一部分被各种类库，工具折叠了，另一部分是因为认识不够，很多实现方案避开了而已，所以代价就是程序的开销变大。因此，加强基本功，走起。
