算法归纳【数组篇】

目录

• 二分查找
• • 1. 前提条件：
  • 2. 二分查找边界
  • 2.移除元素
  • 有序数组的平方
  • 长度最小的子数组
  • 59.螺旋矩阵II
  • • 54. 螺���矩阵

      二分查找

      参考链接

      https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

      1. 前提条件：

      1. 数组为有序数组，
      2. 无重复元素：因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

      2. 二分查找边界

      1. [left, right]区间：while (left high := len(nums)-1 low := 0 for low mid := low + (high-low)/2 if nums[mid] == target { return mid } else if nums[mid] target { high = mid-1 } else { low = mid+1 } } return -1} high := len(nums) low := 0 for low

         ====================================================================

         2.移除元素

         参考链接

         https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

         数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。 所以不可以删除，只能将等于val的值移到后面，最后的结果返回数组满足条件的前半部分即可

         func removeElement(nums []int, val int) int {    left, right := 0, len(nums)-1    for left         if nums[left] == val {            nums[left] = nums[right]            right--        } else {            left++        }    }    return left}    left, right := 0, len(nums)    for left  
         =========================================================
          
         59.螺旋矩阵II
            
         给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
         示例:
         输入: 3
         输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
             
         参考链接
         https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
           
         每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来
          
         //左开右闭func generateMatrix(n int) [][]int {    top, bottom := 0, n-1    left, right := 0, n-1    num := 1    tar := n * n    matrix := make([][]int, n)    for i := 0; i