常见算法整理

[Veveue]

最大数

给定一个非负整数的列表，重新排列它们的顺序把他们组成一个最大的整数。 例如：给定[3,30,34,5,9],最大的组成数是 954330 注意：结果可能非常大，所以你需要返回一个字符串。

[3,30,34,5,9].sort().reverse().join('')

[3,30,34,5,9].sort((a,b) => {
  return (''+b+a) - (''+a+b)
}).join('')

数组排序

常见排序算法

[Veveue]

var twoSum = function(nums, target) {
    if (nums.length === 2) return [0, 1];
    const len = nums.length;
    let map = {};
    for(let i = 0; i < len; i++) {
        let n = target - nums[i];
        let find = map[n];
        if(find !== undefined) return [find, i];
        else map[nums[i]] = i;
    }
};

[Veveue]

缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

// export default (arr) => {
//   // 过滤掉非正整数
//   arr = arr.filter(item => item > 0)
//   // 正整数数组是不是为空
//   if (arr.length) {
//     // 升序，目的：方便从左到右取最小值arr[0]
//     arr.sort((a, b) => a - b)
//     // 如果第一个元素不为1，返回1
//     if (arr[0] !== 1) {
//       return 1
//     } else {
//       // 从左边开始遍历，只要下一个元素和当前元素差值》1说明当前元素的下一个值（+1）
//       for (let i = 0, len = arr.length - 1; i < len; i++) {
//         if (arr[i + 1] - arr[i] > 1) {
//           return arr[i] + 1
//         }
//       }
//       // 如果数组是连续的正整数【1,2,3,4,5,6】
//       return arr.pop() + 1
//     }
//   } else {
//     return 1
//   }
// }
export default (arr) => {
arr = arr.filter(item => item > 0)
// 实现选择排序，先拿到最小值，如果第一个元素不是1直接返回1，如果是1，就要比相邻元素差值
for (let i = 0, len = arr.length, min; i < len; i++) {
min = arr[i]
for (let j = i + 1; j < len; j++) {
if (arr[j] < min) {
let c = min
min = arr[j]
arr[j] = c
}
}
arr[i] = min
if (i > 0) {
if (arr[i] - arr[i - 1] > 1) {
return arr[i - 1] + 1
}
} else {
if (min !== 1) {
return 1
}
}
}
return arr.length ? arr.pop() + 1 : 1
}

var firstMissingPositive = function (nums) { let newList = [], returnVal = 1; nums.map(item => { if (item > 0) { newList[item] = item; } }) for (let i = 1; i <= newList.length; i++) { if (!newList[i]) { returnVal = i; break; } } return returnVal; };