【算法刷题系列】第1天 704. 二分查找，27. 移除元素, 977.有序数组的平方

学习内容

学习文档：数组理论基础

收获总结

• 快速排序：

  快速排序是一种基于分治法的排序算法。首先，选择一个基准元素，然后通过分区操作将数组划分为两部分，一部分元素小于基准值，另一部分元素大于基准值。递归地对这两部分进行排序，最终将数组排序完成。

   1package main
   2
   3import "fmt"
   4
   5func quickSort(arr []int, low, high int) {
   6    if low < high {
   7        pi := partition(arr, low, high)
   8        quickSort(arr, low, pi-1)
   9        quickSort(arr, pi+1, high)
  10    }
  11}
  12
  13func partition(arr []int, low, high int) int {
  14    pivot := arr[high]
  15    i := low - 1
  16    for j := low; j < high; j++ {
  17        if arr[j] < pivot {
  18            i++
  19            arr[i], arr[j] = arr[j], arr[i]
  20        }
  21    }
  22    arr[i+1], arr[high] = arr[high], arr[i+1]
  23    return i + 1
  24}
  

• 二分查找：

  二分查找是一种在有序数组中查找目标值的算法。它通过不断将数组分成两半，并与中间元素进行比较，从而快速缩小查找范围，最终确定目标值的位置。如果目标值不存在，则返回 -1。

   1package main
   2
   3import "fmt"
   4
   5func binarySearch(arr []int, low, high, target int) int {
   6    if low <= high {
   7        mid := low + (high-low)/2
   8        if arr[mid] == target {
   9            return mid
  10        } else if arr[mid] > target {
  11            return binarySearch(arr, low, mid-1, target)
  12        } else {
  13            return binarySearch(arr, mid+1, high, target)
  14        }
  15    }
  16    return -1
  17}
  

• 双指针，对撞指针，快慢指针常用初始化设计：

  1. 双指针：可以从数组两端开始，常用于查找两个数的和问题。初始化 i 为数组起始位置，j 为数组结束位置，当 i < j 时迭代。另一种情况是从同一端开始，适用于查找具有特定差值的元素对。

  2. 快慢指针：快慢指针常用于处理链表或数组中的问题，比如删除重复元素。i 和 j 初始化为数组或链表的起始位置，迭代条件是 j 指针不越界。

   1// 双指针 - 从两端开始
   2func twoSum(arr []int, target int) []int {
   3    i, j := 0, len(arr)-1
   4    for i < j {
   5        sum := arr[i] + arr[j]
   6        if sum == target {
   7            return []int{i, j}
   8        } else if sum < target {
   9            i++
  10        } else {
  11            j--
  12        }
  13    }
  14    return nil
  15}
  16
  17// 双指针 - 从同一端开始
  18func findPairWithDiff(arr []int, diff int) []int {
  19    i, j := 0, 1
  20    for i < len(arr) && j < len(arr) {
  21        if i != j && arr[j]-arr[i] == diff {
  22            return []int{i, j}
  23        } else if arr[j]-arr[i] < diff {
  24            j++
  25        } else {
  26            i++
  27        }
  28    }
  29    return nil
  30}
  31
  32// 快慢指针
  33func removeDuplicates(arr []int) int {
  34    i, j := 0, 1
  35    for j < len(arr) {
  36        if arr[i] != arr[j] {
  37            i++
  38            arr[i] = arr[j]
  39        }
  40        j++
  41    }
  42    return i + 1
  43}
  

题目解析

题目1：704. 二分查找

• 题目描述: 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

• 示例:

  1输入: nums = [-1,0,3,5,9,12], target = 9
  2输出: 4
  

• 解法总结: 使用二分查找方法。初始化左右指针 low 和 high，每次计算中间元素并与目标值进行比较，更新指针范围，直到找到目标值或确认不存在。

• 代码实现:

   1func search(nums []int, target int) int {
   2    low := 0
   3    high := len(nums) - 1
   4    for low <= high {
   5        mid := low + (high-low)/2
   6        if target == nums[mid] {
   7            return mid
   8        } else if target > nums[mid] {
   9            low = mid + 1
  10        } else {
  11            high = mid - 1
  12        }
  13    }
  14    return -1
  15}
  

  时间复杂度: O(log n)，因为每次查找都将搜索范围缩小一半。 空间复杂度: O(1)，只使用了常数空间。

题目2：27. 移除元素

• 题目描述: 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回剩余元素的数量。元素的顺序可能发生改变。

• 示例:

  1输入: nums = [3,2,2,3], val = 3
  2输出: 2, nums = [2,2]
  

• 解法总结: 使用双指针方法。i 和 j 都从数组的头部开始遍历，当 j 指向的元素不等于 val 时，将其赋值给 i 指向的位置，并递增 i，最终返回 i 的值作为新数组的长度。

• 代码实现:

   1func removeElement(nums []int, val int) int {
   2    i, j := 0, 0
   3    count := 0
   4    for j <= len(nums)-1 {
   5        if nums[j] != val {
   6            nums[i] = nums[j]
   7            count++
   8            i++
   9        }
  10        j++
  11    }
  12    return count
  13}
  

  时间复杂度: O(n)，遍历数组一次即可完成操作。 空间复杂度: O(1)，只使用了常数空间。

题目3：977.有序数组的平方

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

• 示例:

  1输入: nums = [-4,-1,0,3,10]
  2输出: [0,1,9,16,100]
  

• 解法总结: 可以采用两种方法。一种是先对所有元素平方后使用快速排序，另一种是使用双指针从数组两端向中间遍历，将较大的平方值放在结果数组的末尾。第二种方法要注意，因为给定的数组是非递减排序的，所以平方值最大的元素一定在数组的两端(中间小)，所以当我们遍历需要for循环从后往前遍历!

• 代码实现:

  方法一：先平方后排序

   1func sortedSquares(nums []int) []int {
   2    for i := 0; i < len(nums); i++ {
   3        nums[i] = nums[i] * nums[i]
   4    }
   5    quickSort(nums, 0, len(nums)-1)
   6    return nums
   7}
   8
   9func quickSort(arr []int, low, high int) {
  10    if low < high {
  11        pivot := partition(arr, low, high)
  12        quickSort(arr, low, pivot-1)
  13        quickSort(arr, pivot+1, high)
  14    }
  15}
  16
  17func partition(arr []int, low, high int) int {
  18    pivotValue := arr[high]
  19    i := low - 1
  20    for j := low; j < high; j++ {
  21        if arr[j] < pivotValue {
  22            i++
  23            arr[i], arr[j] = arr[j], arr[i]
  24        }
  25    }
  26    arr[i+1], arr[high] = arr[high], arr[i+1]
  27    return i + 1
  28}
  

  时间复杂度: O(n log n)，因为对所有元素进行平方操作后，再使用快速排序。 空间复杂度: O(log n)，递归调用栈的空间开销。

  方法二：双指针法

   1func sortedSquares(nums []int) []int {
   2    i, j := 0, len(nums)-1
   3    result := make([]int, len(nums))
   4
   5    for h := len(nums) - 1; h >= 0; h-- {
   6        if nums[i]*nums[i] > nums[j]*nums[j] {
   7            result[h] = nums[i] * nums[i]
   8            i++
   9        } else {
  10            result[h] = nums[j] * nums[j]
  11            j--
  12        }
  13    }
  14    return result
  15}
  

  时间复杂度: O(n)，因为只需要一次遍历即可完成操作。 空间复杂度: O(n)，因为使用了额外的数组来存储结果。