Leetcode数组篇（上）| 8月更文挑战

前言

大家好，我也成为刷题大军的一员了，本次Leetcode数组篇一共分为三篇，此文是上篇，还有中篇和下篇。

每道题目我都会写明题目链接、题目描述以及是属于《剑指Offer》还是Leetcode题库，方便大家查阅观看。

另外，每道题目我都会尽可能地提供多种方案，每种方案的理解程度会从简单到困难，如果你刚好刷到这道题，希望能帮助到你!

最后，建议同种类型的题目一起刷，这样能大概摸索题目的常见套路，做起来效率也更高！

注：本文所有代码使用Golang语言实现

1.找出数组中重复的数字（Offer.03）

题目链接：leetcode-cn.com/problems/sh…

题目描述：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

解题思路： 方法一： 比较简单的思路就是使用暴力循环，即拿第一个数与剩余数字进行比较，如果匹配，视为重复，返回该数字

• 时间复杂度：O（n2）
• 空间复杂度：O（1）

// 方法一：暴力循环
// time: 6.21%   memory: 94.68%
func findRepeatNumber1(nums []int) int {
 target := -1 // 需要用 0 ~ n-1 以外的数
 for i := 0; i <= len(nums); i++ {
  // 注意是 j = i + 1
  for j := i + 1; j < len(nums); j++ {
   head := nums[i]
   tail := nums[j]
   if head == tail {
    target = head
    break
   }
  }
  // 跳出双层循环
  if target != -1 {
   break
  }
 }
 return target
}

方法二： 除了使用暴力循环，使用哈希表（Map）存储也是一种常见思路，数字作为key，重复的次数作为value，遍历该数组，直到value > 1

• 时间复杂度：O（N）
• 空间复杂度：O（N）

// 方法二：哈希表存储
// time: 73.64%  memory: 18.15%
func findRepeatNumber2(nums []int) int {
 target := -1
 repeat := map[int]int{}
 for _, num := range nums {
  if _, ok := repeat[num]; !ok {
   repeat[num] = 1
  } else {
   repeat[num] += 1
  }
  // 满足条件
  if repeat[num] >= 2 {
   target = num
   break
  }
 }
 return target
}

方法三： 先对原数组进行排序，排序后只要比较相邻两个数组是否相同，如果相同，返回该数字

• 时间复杂度：O（N）
• 空间复杂度：O（1）

// 方法三：排序后再比较相邻的数
// time: 73.64%  memory: 53.57%
func findRepeatNumber3(nums []int) int {
 sort.Ints(nums)
 target := -1
 for i := 0; i <= len(nums); i++ {
  if nums[i] == nums[i+1] {
   target = nums[i]
   break
  }
 }
 return target
}

2.二维数组中的查找（Offer.04）

题目链接：leetcode-cn.com/problems/er…

题目描述：

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路： 方法一： 对于简单的数组题，首先考虑的还是暴力循环，通过遍历二维数组，判断数组值与目标值是否一致，如果一致返回；不一致则继续。

• 时间复杂度： O（n*m） 二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小
• 空间复杂度： O（1）

// 方法一：暴力循环
// time: 98.34%  memory: 93.50%
func findNumberIn2DArray1(matrix [][]int, target int) bool {
 // 获取列的长度
 n := len(matrix)
 // 边界情况 [] 或者 [][]
 if n <= 0 {
  return false
 }
 // 获取行的长度
 m := len(matrix[0])
 for i := 0; i < n; i++ {
  for j := 0; j < m; j++ {
   if matrix[i][j] == target {
    return true
   }
  }
 }
 return false
}

方法二： 方法二是对方法一的优化，在遍历二维数组的时候，先判断是否与目标值一致，如果一致返回；如果不一致，则判断是否大于目标值，如果大于的话跳过本轮循环

• 时间复杂度：O（n*m）
• 空间复杂度：O（1）

// 方法二：暴力循环优化
// time: 88.920%  memory: 93.530%
func findNumberIn2DArray2(matrix [][]int, target int) bool {
 // 获取列的长度
 n := len(matrix)
 // 边界情况 [] 或者 [][]
 if n <= 0 {
  return false
 }
 // 获取行的长度
 m := len(matrix[0])
 for i := 0; i < n; i++ {
  for j := 0; j < m; j++ {
   if matrix[i][j] == target {
    return true
   }
   // 因为是递增，所以大于目标值则没有继续比较的必要
   if matrix[i][j] > target {
    break
   }
  }
 }
 return false
}

注：我个人觉得方法二是方法一的优化版，毕竟过滤掉一些不必要的比较的，但是不知道为啥Leetcode跑出来的效果还没方法一好

方法三： 线性查找，线性查找是Leetcode官方提供的解法，解法是先从二维数组的右上角开始比较，如果等于目标值则返回；如果大于目标值，由于数组从上到下递增，所以下面的数可以不用比较，直接往左查找，以此类推。

• 时间复杂度：O（n + m）
• 空间复杂度：O（1）

// 方法三：线性查找
// time: 88.92%  memory: 65.64%
func findNumberIn2DArray3(matrix [][]int, target int) bool {
 if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
  return false
 }
 n := len(matrix)
 m := len(matrix[0])
 row := 0
 column := m - 1
 for row < n && column >= 0 {
  num := matrix[row][column]
  if num == target {
   return true
   // 大于目标值，往左查找
  } else if num > target {
   column -= 1
   // 小于目标值，往下查找
  } else {
   row += 1
  }
 }
 return false
}

注：官方提供的时间复杂度是O（n + m），但是实际跑出的效果看，个人觉得时间复杂度还是 O（n * m）

3.顺时针打印矩阵（Offer.29）

题目链接：leetcode-cn.com/problems/sh…

题目描述：

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解题思路： 方法一：按层模拟。这道题一开始接触会觉得特别难，感觉无从下手，我当时也想到这样一层一层遍历，但第一是觉得麻烦，二是一直在想有没有更简单的办法。

不过有些题目还是要静下心去计算和推敲，就像这道题，其实画出这张图，解法就比较清晰明了。

20210801111621.png

• 时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
• 空间复杂度：O(1)。

// 按层模拟
// time: 80.63%  memory: 54.81%
func spiralOrder(matrix [][]int) []int {
 // 边界条件
 if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
  return []int{}
 }

 nums := make([]int, 0)
 // 二维数组的行数和列数
 rows := len(matrix)
 columns := len(matrix[0])
 // 根据画出的图，可以得到这四个指针
 left := 0
 right := columns - 1
 top := 0
 bottom := rows - 1
 // 跳出循环的边界条件:
 // left <= right: 二维数组的行可以遍历
 // top <= bottom: 二维数组的列可以遍历
 for left <= right && top <= bottom {
  // 从左往右遍历
  for col := left; col <= right; col++ {
   nums = append(nums, matrix[top][col])
  }
  // 从右上角往下遍历
  // 第一层已经遍历完，所以下一次遍历要从第二层开始，所以 row := top + 1;
  for row := top + 1; row <= bottom; row++ {
   nums = append(nums, matrix[row][right])
  }
  // 再继续遍历的时候，需要判断是否满足条件
  if left < right && top < bottom {
   // 从右往左遍历
   for col := right - 1; col > left; col-- {
    nums = append(nums, matrix[bottom][col])
   }
   // 从下往上遍历
   for row := bottom; row > top; row-- {
    nums = append(nums, matrix[row][left])
   }
  }
  left++
  right--
  top++
  bottom--
 }
 return nums
}

注：该解法来自于官方解答，其实官方解答还有另一种解法，但我觉得比较复杂，就没列举出来了

写在最后

本篇内容就先讲这三道题，如果错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！

其他文章