tm的学习笔记

Appearance

排序与搜索 ​

概念 ​

  • 排序：把某个乱序的数组变成升序或者降序的数组。
  • 搜索：找出数组中某个元素的下标。

排序算法：冒泡、选择、插入、归并、快速排序... 搜索算法：顺序、二分搜索... 动画：

JS 中的排序和搜索 ​

  • JS 中的排序：数组的 sort 方法。
  • JS 中的搜索：数组的 indexOf 方法。

冒泡排序 ​

思路

  • 比较相邻元素，如果第一个比第二个大，则交换。
  • 一轮下来，可以保证最后一个数是最大的。
  • 执行 n - 1 轮，就可以完成排序。
javascript
// 冒泡排序
Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
};

const arr = [5, 4, 3, 2, 1];
arr.bubbleSort();
console.log(arr); // [ 1, 2, 3, 4, 5 ]
// 时间复杂度 O(n^2)

插入排序在排序小型数组时比冒泡、选择排序要好

选择排序 ​

思路

  • 找到数组中的最小值，将其移到第一位。
  • 接着找到数组中第二小值，将其移到第二位。
  • .....
javascript
// 选择排序
Array.prototype.selectionSort = function () {
  // this.length - 1 是因为最后一个一定是最大的 
  for (let i = 0; i < this.length - 1; i++) {
    let indexMin = i;
    for (let j = i; j < this.length; j++) {
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }
    if (indexMin !== i) {
      const temp = this[i];
      this[i] = this[indexMin];
      this[indexMin] = temp;
    }
  }
};

const arr = [5, 4, 3, 2, 1];
arr.selectionSort(arr);
console.log(arr); // [ 1, 2, 3, 4, 5 ]
// 时间复杂度 两个循环 O(n^2)

插入排序 ​

  • 从第二个数开始往前比。
  • 比它大就往后排，否则终止进行下一轮。
  • 以此类推进行到最后一个数
javascript
// 插入排序
Array.prototype.insertionSort = function () {
  // i = 1 从第二位开始 
  for (let i = 1; i < this.length; i += 1) {
    const temp = this[i];
    let j = i;
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1];
      } else {
        break;
      }
      j -= 1;
    }
    this[j] = temp;
  }
};

// const arr = [5, 4, 3, 2, 1];
const arr = [2, 4, 5, 3, 1];
arr.insertionSort(arr);
console.log(arr); // [ 1, 2, 3, 4, 5 ]
// 时间复杂度 两个循环 O(n^2)

归并排序 ​

思路

  • 分：把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数。
  • 合：把两个数合并成有序数组，再对有序数组进行合并，直到全部子数组合并成一个完整的数组。

合并两个有序数组

  • 新建一个空数组 res，用于存放最终排序后的数组。
  • 比较两个有序数组的头部，较小者出队并推入 res 中。
  • 如果两个数组还有值，就重复第二步。
javascript
// 归并排序

Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) return arr;
    let res = [];
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = rec(left);
    const orderRight = rec(right);

    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
        );
      } else if (orderLeft.length) {
        res.push(orderLeft.shift());
      } else {
        res.push(orderRight.shift());
      }
    }
    return res;
  };
  const res = rec(this);
  res.forEach((n, i) => (this[i] = n));
};

const arr = [5, 4, 3, 2, 1];
arr.mergeSort(arr);
console.log(arr); // [ 1, 2, 3, 4, 5 ]

// 时间复杂度
//  分的时间复杂度是 O(logN)
//  合的时间复杂度是 O(n)
//  总共时间复杂度是 O(n * logN)

快速排序 ​

思路

  • 从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面。
  • 递归：递归地对基准前后的子数组进行分区。
javascript
// 归并排序

Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) return arr;
    let left = [];
    let right = [];
    let mid = arr[0];
    // 注意这里 i 从 1 开始
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...rec(left), mid, ...rec(right)];
  };
  const res = rec(this);
  res.forEach((n, i) => (this[i] = n));
};

// const arr = [5, 4, 3, 2, 1];
const arr = [2, 4, 5, 3, 1];
arr.quickSort(arr);
console.log(arr); // [ 1, 2, 3, 4, 5 ]

// 时间复杂度
//   递归的时间复杂度是O(logN)
//   分区操作的时间复杂度是O(n)
//   时间复杂度：O(n * logN)

顺序搜索 ​

思路

  • 遍历数组
  • 找到跟目标值相等的元素，就返回它的下标。

二分搜索 ​

思路

  • 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
  • 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
javascript
// 二分搜索
Array.prototype.binarySearch = function (target) {
  let low = 0;
  let high = this.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const element = this[mid];
    if (target > element) {
      low = mid + 1;
    } else if (target < element) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
};

const arr = [1, 2, 3, 4, 5];
console.log(arr.binarySearch(4)); // 3
console.log(arr.binarySearch(0)); // -1

// 时间复杂度
//  每次比较都使搜索范围缩小一半。
//  时间复杂度：O(logN)

LeetCode：21.合并两个有序链表 ​

javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    const res = new ListNode(0)
    let p = res
    let p1 = list1
    let p2 = list2
    while(p1 && p2) {
        if (p1.val > p2.val) {
            p.next = p2
            p2 = p2.next
        } else {
            p.next = p1
            p1 = p1.next
        }
        p = p.next
    }

    // 如果链表一长一短，剩下的一个，直接拼上即可，不需要再遍历了
    if (p1) {
        p.next = p1
    }
    if (p2) {
        p.next = p2
    }
    return res.next
};

// 时间复杂度 O(n)
// 空间复杂度 O(1)

LeetCode：374.猜数字大小 ​

思路

  • 二分查找
  • 调用 guess 函数，来判断中间元素是否是目标值。

解题步骤

  • 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束。
  • 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
javascript
/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */

var guessNumber = function(n) {
    let low = 1
    let high = n
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        const res = guess(mid)
        if (res === 0) {
            return mid
        } else if (res === -1) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    // 一定是有值的，所以不用考虑无值的情况
};

// 时间复杂度 logN
// 空间复杂度 O(1)