⑪ 进阶算法之“搜索算法”

进阶算法之“搜索算法”

一、理论

1. 排序和搜索简介

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

1.1 js中的排序和搜索

  • js中的排序:sort()
  • js中的搜索:indexOf()

1.2 排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 快速排序

1.3 搜索算法

  • 顺序搜索
  • 二分搜索

2. js实现排序

2.1 冒泡排序

2.2.1 思路
  • 比较相邻元素,如果第一个比第二个大,则交换他们
  • 一轮下来,保证最后一个数是最大的
  • 执行n-1轮即完成排序
2.2.2 动画演示

冒泡排序动画演示

2.2.3 coding part
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
      }
    }
  }
}
2.2.4 时间复杂度
  • 时间复杂度:O(n^2)

2.2 选择排序

2.2.1 思路
  • 找到数组的最小值,选中并将其放在第一位
  • 找到数组的第二小值,选中并将其放在第二位
  • 以此类推,执行n-1轮
2.2.2 动画演示

选择排序动画演示

2.2.3 coding part
Array.prototype.selectionSort = function () {
  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
    }
  }
}
2.2.4 时间复杂度
  • 时间复杂度:O(n^2)

2.3 插入排序

2.3.1 思路
  • 从第二个数开始往前比
  • 比他大就往后排
  • 以此类推进行到最后一个数
2.3.2 动画演示

插入排序动画演示

2.3.3 coding part
Array.prototype.insertionSort = function () {
  for(let i = 1; i < this.length; i++) {
    const temp = this[i]
    let j = i
    while(j > 0) {
      if(this[j-1] > temp) {
        this[j] = this[j-1]
      } else {
        break
      }
      j--
    }
    this[j] = temp
  }
}
2.3.4 时间复杂度
  • 时间复杂度:O(n^2)

2.4 归并排序

2.4.1 思路
  • 分:把数组劈成两半,再递归得将子数组进行“分”操作,直到分成一个个单独的数
  • 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并成一个完整数组
合并两个有序数组
  • 新建一个空数组res,用于存放最终排序后的数组
  • 比较两个有序数组的头部,较小者出队并推入res中
2.4.2 动画演示

归并排序动画演示

2.4.3 coding part
Array.prototype.mergeSort = function () {
  const rec = arr => {
    if(arr.length == 1) return arr
    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)
    const res = []
    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 if(orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res = rec(this)
  res.forEach((n, i) => this[i] = n)
}
2.4.4 时间复杂度
  • 分的时间复杂度:O(logn)
  • 合的时间复杂度:O(n)
  • 时间复杂度:O(nlogn)

2.5 快速排序

2.5.1 思路
  • 分区:从数组中任意选择一个基准,所有比基准小的元素放在基准前,比基准小的元素放在基准后
  • 递归:递归地对基准前后的子数组进行分区
2.5.2 动画演示

快速排序动画演示

2.5.3 coding part
Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if(arr.length == 1) return arr
    const left = []
    const right = []
    const mid = arr[0];
    for(let i = 1; i < this.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)
}
2.5.4 时间复杂度
  • 递归的时间复杂度:O(logn)
  • 分区的时间复杂度:O(n)
  • 时间复杂度:O(nlogn)

3. js实现搜索

3.1 顺序搜索

3.1.1 思路
  • 遍历数组
  • 找到跟目标值相等的元素,返回其下标
  • 遍历结束后,若没有找到相等元素则返回-1
3.1.2 coding part
Array.prototype.sequentialSearch = function(item) {
  for(let i = 0; i < this.length; i++) {
    if(this[i] === item) {
      return i
    }
  }
  return -1
}
3.1.3 时间复杂度
  • 时间复杂度:O(n)

3.2 二分搜索

前提:数组有序

3.2.1 思路
  • 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
  • 如果目标值大于或小于中间元素,则在大于或小于中间元素的那一半数组中搜索
3.2.2 coding part
Array.prototype.binarySearch = function(item) {
  let low = 0, high = this.length - 1
  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const element = this[mid]
    if(element < item) {
      low = mid + 1
    } else if(element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}
3.2.3 时间复杂度
  • 时间复杂度:O(logn)

二、刷题

1. 合并两个有序链表(21)

1.1 题目描述

  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

1.2 解题思路

  • 与归并排序中合并两个有序数组很相似
  • 将数组替换成链表

1.3 解题步骤

  • 新建一个新链表,作为返回结果
  • 用指针遍历两个有序数组,并比较两个链表当前节点,较小者先接入新链表并将指针后移一步
  • 链表遍历结束,返回新链表
function mergeTwoLists(l1, l2) {
  const res = new ListNode(0);
  let p = res, p1 = l1, p2 = l2;
  while(p1 && p2) {
    if(p1.val < p2.val) {
      p.next = p1;
      p1 = p1.next;
    } else {
      p.next = p2;
      p2 = p2.next;
    }
    p = p.next;
  }
  if(p1) {
    p.next = p1;
  }
  if(p2) {
    p.next = p2
  }
  return res.next
}

1.4 时间复杂度&空间复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

2. 猜数字大小(374)

2.1 题目描述

  • 猜数字游戏的规则如下:
    • 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
    • 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
    • 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):
      • -1:我的数字比较小 pick < num
      • 1:我的数字比较大 pick > num
      • 0:恭喜!你猜对了!pick == num

2.2 解题思路

输入:n = 10, pick = 6
输出:6

  • 二分搜索
  • 调用guess函数来判断中间元素是否是目标值

2.3 解题步骤

  • 二分搜索
function guessNumber(n) {
  let low = 1, high = n;
  while(low <= high) {
    const mid = Math.floor((low + high) / 2);
    const res = guess(mid)
    if(res === 0) {
      return mid
    } else if(res === 1) {
      low = mid + 1
    } else if(res === -1) {
      high = mid - 1
    }
  }
}

2.4 时间复杂度&空间复杂度

  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

三、总结 -- 技术要点

上一篇:字符串的调整与替换:将所有的“*“字符挪到左边,数字字符挪到右边(Java)


下一篇:3. 无重复字符的最长子串【中等】