preface

Hello, everyone, I have become a member of the problem brushing army, this Leetcode array is divided into three parts, this is the first part, and the middle part and the next part.

For each topic, I will specify the title link, title description and whether it belongs to “Finger Offer” or Leetcode question bank, so that you can check it.

In addition, I will try my best to provide a variety of solutions for each question, and the understanding level of each solution will range from simple to difficult. If you happen to brush this question, I hope to help you!

Finally, it is suggested that the same type of topics brush together, so that we can probably explore the common routine of the topic, and do it more efficiently!

Note: All the code in this article is implemented in Golang language

1. Find duplicate numbers in array (offer.03)

Title link: leetcode-cn.com/problems/sh…

Title description:

Find duplicate numbers in the array. All numbers in an array of length N, nums, are in the range 0 to n-1. Some numbers in the array are repeated, but we don't know how many are repeated, or how many times each number is repeated. Please find any duplicate number in the array.Copy the code

Method 1: A relatively simple idea is to use a violence loop, that is, compare the first number with the rest of the number, if the match, as a repeat, return the number

  • Time complexity: O (N2)
  • Space complexity: O (1)
// Time: 6.21% memory: 94.68% func findRepeatNumber1(nums []int) int {target := -1 // For I := 0; i <= len(nums); J = I + 1 for j := I + 1; j < len(nums); J ++ {head := nums[I] tail := nums[j] if head == tail {target = head break}} = -1 { break } } return target }Copy the code

A hash table (Map) is also a common way to store data, with the number as the key and the number of repetitions as the value, iterating through the array until value > 1

  • Time complexity: O (N)
  • Space complexity: 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}Copy the code

Method 3: sort the original array first, then compare the two adjacent arrays to see if they are the same, if so, return the number

  • Time complexity: O (N)
  • Space complexity: O (1)
// Time: 73.64% memory: 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 }Copy the code

2. Lookup in a two-dimensional array (offer.04)

Title link: leetcode-cn.com/problems/er…

Title description:

In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.Copy the code

Method 1: For simple array problems, first consider the violence cycle, by traversing the two-dimensional array, determine whether the array value is consistent with the target value, if so, return; If not, continue.

  • Time complexity: Every element in O (n*m) two-dimensional array is iterated, so the time complexity is the size of the two-dimensional array
  • Space complexity: O (1)
// Time: 98.34% memory: 93.50% func findNumberIn2DArray1 (matrix [] [] int, Target int) bool {// Get column length n := len(matrix) // boundary case [] or [][] if n <= 0 {return false} // Get row length 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 }Copy the code

Method 2: Method 2 is the optimization of method 1. When traversing the two-dimensional array, first judge whether it is consistent with the target value. If so, return; If not, it determines whether the value is greater than the target value and skips the loop if it is

  • Time complexity: O (n*m)
  • Space complexity: O (1)
// Time: 88.920% memory: 93.530% func findNumberIn2DArray2 (matrix [] [] int, Target int) bool {// Get column length n := len(matrix) // boundary case [] or [][] if n <= 0 {return false} // Get row length m := len(matrix[0]) for i := 0; i < n; i++ { for j := 0; j < m; J ++ {if matrix[I][j] == target {return true} Matrix [I][j] > target {break}} return false}Copy the code

Note: I personally think method 2 is the optimized version of method 1. After all, it filters out some unnecessary comparisons, but I don’t know why the effect of Leetcode is not as good as method 1

Method 3: Linear search, linear search is the official solution provided by Leetcode, the solution is to start from the upper right corner of the two-dimensional array, if equal to the target value will return; If it is larger than the target value, since the array increases from top to bottom, the numbers below can be looked up to the left without comparison, and so on.

  • Time complexity: O (n + m)
  • Space complexity: 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 { Else if num > target {column -= 1} else {row += 1} return false}Copy the code

Note: The time complexity provided by the official is O (n + m), but the actual running effect, I think the time complexity is still O (n * m).

3. Print matrix clockwise (offer.29)

Title link: leetcode-cn.com/problems/sh…

Title description:

Enter a matrix and print out each number in clockwise order from the outside in.Copy the code

Method 1: simulate by layer. At the beginning, I felt it was very difficult to touch this problem, and I didn’t know how to start. At that time, I also thought of going through it layer by layer, but first, I felt it was troublesome, and second, I kept thinking whether there was an easier way.

However, some problems still need to calm down to calculate and deliberate, just like this problem, in fact, draw this picture, the solution is relatively clear.

20210801111621.png

  • Time complexity: O(Mn), where M and n are the number of rows and columns of the input matrix respectively. Each element in the matrix is accessed once.
  • Space complexity: O(1).
// Time: 80.63% memory: 54.81% func spiralOrder (matrix [] [] int) int [] {the if / / boundary conditions for the 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 // top <= bottom: for left <= right &&top <= bottom {// For left := 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[col]])} // For row := bottom; row > top; row-- { nums = append(nums, matrix[row][left]) } } left++ right-- top++ bottom-- } return nums }Copy the code

Note: this solution is from the official solution. In fact, there is another solution to the official solution, but I think it is more complicated, so I did not list it

Write in the last

This content first speak these three questions, if wrong, trouble in the comment area pointed out that the words of some grateful, in addition, if this article is useful to you, also trouble guests point a small love 💖!

Other articles

August Leetcode array (piece of) | more challenges