「🦆TSK的博客」

Appearance

On this page

数组 ​

关于数组的算法

排序算法 ​

🔗插入排序 ​

TIP

arr[i-1] = arr[i] 就是相当于往前移动一位
可以想象，arr[2] = arr[3], arr[2] 的位置被 arr[3] 取代,那就是往前移动了一位

下面我们尝试基于插入排序的思路，对如下数组进行排序：

js
[5, 3, 2, 4, 1]

注意这里按照插入排序的原则，靠前的较大数字要为靠后的较小数字腾出位置：

js
[暂时空出, 5, 2, 4, 1]
当前元素 3

结果

js
[3, 5, 2, 4, 1]

以上我们就完成了一轮插入。这一轮插入结束后，大家会发现，有序数组 [5] 现在变成了有序数组 [3, 5]。

沿着这个思路，继续往下走，当前元素变成了紧跟[3, 5] 这个有序序列的 2。对比 2 和 5 的大小，发现 2 比 5 小。按照插入排序的原则，5要往后挪，给较小元素空出一个位置：

js
[3, 暂时空出, 5, 4, 1]
当前元素 2

接着继续向前对比，遇到了 3。对比 3 和 2 的大小，发现 3 比 2 大。按照插入排序的原则，3要往后挪，给较小元素空出一个位置：

js
[暂时空出, 3, 5, 4, 1]
当前元素 2

此时 2 前面的有序序列已经被对比完毕了。我们把 2 放到最终空出来的那个属于它的空位里去：

js
[2, 3, 5, 4, 1]

以上我们完成了第二轮插入。这一轮插入结束后，有序数组 [3, 5] 现在变成了有序数组 [2, 3, 5]。

....

在有序序列里定位元素位置的时候，是从后往前定位的。只要发现一个比当前元素大的值，就需要为当前元素腾出一个新的坑位。
js
let s = ["a", "b", "c"]; // ["b","c","a"]

let s1 = s[0];

for (let i = 1; i < s.length; i++) {
  s[i - 1] = s[i];
}
s[s.length - 1] = s1;

s; // ["b","c","a"]
javascript
function insertSort(arr) {
  // 缓存数组长度
  const len = arr.length
  // temp 用来保存当前需要插入的元素
  let temp  
  // i用于标识每次被插入的元素的索引
  for(let i = 1;i < len; i++) {
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i
    temp = arr[i]

    // 判断 j 前面一个元素是否比 temp 大
    while(j > 0 && arr[j-1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j-1]   
      j--
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp
  }
  return arr
}

冒泡排序 ​

冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。

第一次循环后，把最大的数放到最后，第二次循环，把第二大的数放到倒数第二位，依次类推。就像冒泡一样

js
for (let j = 0; j < nums.length; j++) {
  for (let i = 0; i < nums.length - 1 - j; i++) {
    let num1 = nums[i];
    let num2 = nums[i + 1];

    if (num1 > num2) {
      nums[i] = num2;
      nums[i + 1] = num1;
    }
  }
}

优化排序算法

js
function betterBubbleSort(arr) {
  const len = arr.length  
    
  for(let i=0;i<len;i++) {
    // 区别在这里，我们加了一个标志位
    let flag = false
    for(let j=0;j<len-1-i;j++) {
        if(arr[j] > arr[j+1]) {
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
          // 只要发生了一次交换，就修改标志位
          flag = true
        }
    }
        
    // 若一次交换也没发生，则说明数组有序，直接放过
    if(flag == false)  return arr;
  }
  return arr
}

选择排序 ​

每一次找到最大的值,把最后的值与找到的最大的值进行交换

在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

javascript
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

二分查找 ​

左闭右闭区间 ​

因为这个 right 是可以访问到的,所以 right = mid -1

js
var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let mid, left = 0, right = nums.length - 1;
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while (left <= right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

左闭右开区间 ​

right 访问不到,所以可以 使用 right = mid

js
var search = function(nums, target) {
  // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
  let mid, left = 0, right = nums.length;
  // 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况
  while (left < right) {
    // 位运算 + 防止大数溢出
    mid = left + ((right - left) >> 1);
    // 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
    // 由于right本来就不在查找范围内，所以将右边界更新为中间值
    // 如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
    if (nums[mid] > target) {
      right = mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
};

🔥双指针 ​

双指针法(快慢指针法): 通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作

定义快慢指针

  • 快指针：寻找新数组的元素, 新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置

移除元素 ​

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返 回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地 修改输入数组

思路

快指针去遍历寻找新的元素, 慢指针是所有不等于 val 的下标

ts
function removeElement(nums: number[], val: number): number {
  let slowIndex = 0
  for(let fastIndex = 0;fastIndex< nums.length;fastIndex ++ ){
    if(nums[fastIndex] !== val){
      nums[slowIndex ++ ] = nums[fastIndex]
    }
  }
  return slowIndex
};

移动 0 ​

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相 对顺序。

思路

交换位置, 慢指针 指向最近的不为 0 的值的下标,然后与快指针所对应的 值交换

比如: arr = [1,0,2,0,5] fastIndex = 2 slowIndex = 1 然后 arr[2] 与 arr[1] 进行交换

ts
function moveZeroes(nums: number[]): void {
    let slowIndex = 0;
    for(let fastIndex = 0;fastIndex < nums.length;fastIndex ++){
        if(nums[fastIndex] !== 0){
            [nums[fastIndex],nums[slowIndex]] =  [nums[slowIndex],nums[fastIndex]]
            slowIndex++
        }
    }
};

删除有序数组中的重复项 ​

ts
var removeDuplicates = function(nums) {
  let n = 0
  for(let i =0;i<nums.length;i++){
    if(nums[i] == nums[i+1])continue;
    nums[n++] = nums[i]
  }
  return n
}

有序数组的平方 ​

给你一个按 非递减顺序 排序的整数数组 nums, 返回 每个数字的平方 组成的新数组， 要求也按非递减顺序 排序。

思路

数组是有序的,那么数组平方的最大值是在数组的两端,不是在左边就是在右边

遇见有序数组可以使用双指针
如果是无序的，则无法使用，因为最大值不是在 左端 或者是在 右端

ts
function sortedSquares(nums: number[]): number[] {
  let i = 0,
    j = nums.length - 1,
    result: Array<number> = [],
    k = nums.length - 1;

// 必须使用 i <= j 否则中间的值 取不到
  while (i <= j) {
    let left = Math.pow(nums[i], 2);
    let right = Math.pow(nums[j], 2);

    if (left < right) {
      result[k--] = right;
      j--;
    } else {
      result[k--] = left;
      i++;
    }
  }
  return result;
}

let r = sortedSquares([-4, -1, 0, 3, 10]);

滑动窗口 ​

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置

滑动窗口主要确定三点:

  1. 窗口内是什么
  2. 如何移动窗口内的起始位置
  3. 如何移动窗口内的结束位置

模版 ​

最长模版:

js
初始化 left,right,result,bestResult

while(右指针没有到结尾){
  窗口扩大,加入 right 对应的元素,更新当前 result
  while(result不满足要求){
    窗口缩小,移出 left 对应的元素,left 右移
  }
  更新最优结果 bestResult
  指针右移
}
返回bestResult

最短模版:

js
初始化 left,right,result,bestResult

while(右指针没有到结尾){
  窗口扩大,加入 right 对应的元素,更新当前 result
  while(result满足要求){ 
    更新最优结果 bestResult
    窗口缩小,移出 left 对应的元素,left 右移
  }
  指针右移
}
返回bestResult
js
let sum = 7,
  nums = [2, 3, 1, 2, 4, 3];
let left = 0,
  right = 0,
  result = 0,
  bestResult = 0;

while (right < nums.length) {
  // 指针扩大
  result += nums[right]; 
  // 结果满足要求
  while (result >= sum) {
    // 更新最优结果
    if (right - left + 1 < bestResult || bestResult === 0) {
      bestResult = right - left + 1;
    }
    // 移除left对应元素
    result -= nums[left];
    // 左指针右移
    left++;
  }
  // 右指针右移
  right++;
}

长度最小的子数组 ​

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度 最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

  • 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度 最小的子数组
ts
function minSubArrayLen(nums: number[], num: number): any {
  let sum = 0,
    len = Infinity,
    j = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    while (sum >= num) {
      len = Math.min( len, i - j + 1 );
      // 不断的滑动窗口，直到满足, j 一定是递增的
      sum -= nums[j++];
    }
  }
  return len;
}
let r = minSubArrayLen([2, 3, 1, 2, 4, 3], 7);

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于 s 了，窗口就要向前移动了(也就是该缩 小了)。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索 引。

滑动窗口最大值 ​

题目： 给定一个数组 nums，有一个大小为 k 的滑动窗口，从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口中的k个数字。滑动窗口每次只向右移动一位，求返回滑动窗口最大值
输入： nums: [1,3,-1,-3,5,3,6,7]； k: 3
输出： [3, 3, 5, 5, 6, 7]

js
function maxSlidingWindow(nums, k) {
  // window存储当前窗口中数据的下标
  const window = [];
  // result存储窗口中的最大值
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    if (i - window[0] > k - 1) {
      // 剔除窗口长度超出范围时左侧的最大值
      window.shift(); 
    }
    for (let j = window.length - 1; j >= 0; j--) {
      // 当前窗口的值依次和要插入的值做比较，如果小于要插入的值，剔除掉该值，直到window为空为止（保证window中最左侧的值为最大值）
      if (nums[window[j]] <= nums[i]) {
        window.pop();
      }
    }
    // 添加右侧新加入的值，插入新值时有两种情况：
    // 1、新值为最大值时，则window此时为空；
    // 2、新值不为最大值时，window已剔除掉比新值小的值
    window.push(i);
    if (i >= k - 1) {
      // 窗口是从0开始移动，当移动的距离大于等于目标范围后，以后再往后移动一次，就要写入当前窗口的最大值
      result.push(nums[window[0]]);
    }
  }
  return result;
}

合并两个有序数组 ​

既然是有序,就要考虑使用双指针充分利用这个条件

ts
function merge(nums1: number[], m: number, nums2: number[], n: number): any {
  let arr = [],
    left = 0,
    right = 0,
    cur;

  while (left < m || right < n) {
    if (m == left) {
      cur = nums2[right++];
    } else if (n == right) {
      cur = nums1[left++];
    } else if (nums1[left] <= nums2[right]) {
      cur = nums1[left++];
    } else if (nums1[left] > nums2[right]) {
      cur = nums2[right++];
    }
    // left + right - 1  要减一
    arr[left + right - 1] = cur;
  }
  // 这个时候 arr 已经和 num1 一样了
  for (let i = 0; i != m + n; i++) {
    nums1[i] = arr[i];
  }
  return nums1;
}

merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)

Updated at: