Skip to main content

算法

常见的基础算法：递归、排序、枚举

时间复杂度​

常见的时间复杂度：

  • 常数阶：O(1)
  • 对数阶：O(logN)
  • 线性阶：O(n)
  • 线性对数阶：O(nlogN)
  • 平方阶：O(n^2)
  • 立方阶：O(n^3)
  • 指数阶：O(2^N)

复杂度分析技巧：

  1. 看有几重循环，一重是 O(n)，两重是 O(n^2)，以此类推
  2. 如果有二分，则为 O(logN)
  3. 保留最高项，去掉常数项

空间复杂度​

快速排序​

流程：

  1. 随机选择数组中的一个数 A，以这个数为基准
  2. 将其他数字跟这个数进行比较，比这个数小的放在其左边，大的放在其右边
  3. 经过一次循环后，A 的左边都是小于 A 的，右边都是大于 A 的
  4. 继续将左边和右边的数递归前面的过程

实现代码：

// 比较函数
function compare(a, b) {
  if (a === b) {
    return 0;
  }
  return a < b ? -1 : 1;
}

// 原地交换函数
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]];
}

// 划分操作函数
function partition(array, left, right) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compare(array[i], pivot) === -1) {
      i++;
    }
    while (compare(array[j], pivot) === 1) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }

  return i;
}

function quick(array, left, right) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right);
    if (left < index - 1) {
      quick(array, left, index - 1);
    }
    if (index < right) {
      quick(array, index, right);
    }
  }
  return array;
}

function quickSort(array) {
  return quick(array, 0, array.length - 1);
}

使用：

const data = [25, 18, 66, 45, 77, 31, 96, 52];
console.log(quickSort(data));

二分查找​

二分查找采用分治思想，时间复杂度是 O(logN)

场景：在一堆有序的数中找出指定的数

流程：

  1. 找到数组中间的数 A，与要找的数比较大小
  2. 如果 A 较大，则从前半部分查找，否则从后半部分查找
  3. 不断缩小数量级，每次比较都扔掉一半的数据，直到找完数组为止

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function find(target, array) {
  let i = 0;
  let j = array[i].length - 1;
  while (i < array.length && j >= 0) {
    if (array[i][j] === target) {
      return [i, j];
    } else if (array[i][j] > target) {
      j--;
    } else {
      return true;
    }
  }
  return false;
}

const data = [
  [1, 2, 3, 4],
  [5, 9, 10, 11],
  [13, 20, 21, 23]
];

console.log(find(10, data));

冒泡排序​

选择排序​

插入排序​

归并排序​

归并排序采用分治思想。将一个数组分成 2 个，再分成 4 个，依次下去，直到分割成一个一个的数据， 再将这些数据两两合并，直到归并成原始数组。

将小数组合并成大数组，先创建一个临时数组 C，比较 A[0]，B[0]，将较小值放到 C[0]，再比较 A[1]与 B[0]，将较小值放到 C[1]，直到对 A，B 都遍历一遍。

方式一：

function sortArray(nums) {
  if (nums.length < 2) return nums;
  let middle = Math.floor(nums.length / 2);
  let left = [],
    right = [];
  left = nums.slice(0, middle);
  right = nums.slice(middle);
  return merge(sortArray(left), sortArray(right));
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

let arr = [2, 1, 4, 5, 3, 1, 5, 6, 0];
let res = sortArray(arr);
console.log(res); // [0, 1, 1, 2, 3, 4, 5, 5, 6]

方式二、

function mergeArray(arr, first, mid, last, temp) {
  let i = first;
  let m = mid;
  let j = mid + 1;
  let n = last;
  let k = 0;
  while (i <= m && j <= n) {
    if (arr[i] < arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }
  while (i <= m) {
    temp[k++] = arr[i++];
  }
  while (j <= n) {
    temp[k++] = arr[j++];
  }
  for (let l = 0; l < k; l++) {
    arr[first + l] = temp[l];
  }
  return arr;
}

function mergeSort(arr, first, last, temp) {
  if (first < last) {
    let mid = Math.floor((first + last) / 2);
    mergeSort(arr, first, mid, temp); // 左子数组有序
    mergeSort(arr, mid + 1, last, temp); // 右子数组有序
    arr = mergeArray(arr, first, mid, last, temp);
  }
  return arr;
}

let arr = [2, 1, 4, 5, 3, 1, 5, 6, 0];
let temp = [];
let SortedArr = mergeSort(arr, 0, arr.length - 1, temp);
console.log(SortedArr); // [0, 1, 1, 2, 3, 4, 5, 5, 6]

数组生成树形结构​

const arr = [
  { id: 1, value: '节点1', pid: 0 },
  { id: 2, value: '节点2', pid: 1 },
  { id: 3, value: '节点3', pid: 1 },
  { id: 4, value: '节点4', pid: 2 },
  { id: 5, value: '节点5', pid: 0 },
  { id: 6, value: '节点6', pid: 5 },
  { id: 7, value: '节点7', pid: 6 },
  { id: 8, value: '节点8', pid: 6 }
];

期望结果如下：

[
  {
    "id": 1,
    "value": "节点1",
    "pid": 0,
    "children": [
      {
        "id": 2,
        "value": "节点2",
        "pid": 1,
        "children": [
          {
            "id": 4,
            "value": "节点4",
            "pid": 2,
            "children": []
          }
        ]
      },
      {
        "id": 3,
        "value": "节点3",
        "pid": 1,
        "children": []
      }
    ]
  },
  {
    "id": 5,
    "value": "节点5",
    "pid": 0,
    "children": [
      {
        "id": 6,
        "value": "节点6",
        "pid": 5,
        "children": [
          {
            "id": 7,
            "value": "节点7",
            "pid": 6,
            "children": []
          },
          {
            "id": 8,
            "value": "节点8",
            "pid": 6,
            "children": []
          }
        ]
      }
    ]
  }
]

方式一、递归实现

function buildTree(arr, pid = 0) {
  const tree = [];
  for (const item of arr) {
    if (item.pid === pid) {
      const children = buildTree(arr, item.id);
      if (children.length > 0) {
        item.children = children;
      } else {
        item.children = [];
      }
      tree.push(item);
    }
  }
  return tree;
}

方式二、reduce 循环

function buildTree(arr) {
  return arr
    .reduce((prev, next) => {
      let finder = arr.find(item => item.id === next.pid);
      if (finder) {
        (finder.children || ((finder.children = []), finder.children)).push(next);
        prev.every(next => next.id !== finder.id) && prev.push(finder);
      }
      return prev;
    }, [])
    .reduce((prev, next, i, arr) => (arr.every(item => item.id !== next.pid) && prev.push(next), prev), []);
}

动态规划​

贪心算法​