preface

Hello, everyone, I have become a member of the problem brushing army, this Leetcode array is divided into three parts, this article is the middle part, as well as the first and the second 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

4. Find the number in the sorted array (offer.53_1)

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

Title description:

Count the number of occurrences of a number in a sorted array. Tip: - NUMs is a non-decrement array (critical)Copy the code

Method 1: For simple array problems, the first consideration is to traverse the number group, and use hash table (Map) storage, the number as the key, the number of occurrences as the value, each occurrence, value+1, and finally query the hash table to obtain the occurrence number

  • Time complexity: O (n)
  • Space complexity: O (n)
// time: 45.58% memory: Search1 (nums []int, target int) int{numMap := map[int]int{} for _, num := range nums { if _, ok := numMap[num]; ! Else {numMap[num] += 1}} count := 0 if _, ok := numMap[target]; ok { count = numMap[target] } return count }Copy the code

Method 2: Because the array is increasing, so the same number must be adjacent, and as long as the number traversed is greater than the target value, the following number need not be compared, you can exit in advance.

  • Time complexity: O (n)
  • Space complexity: O (1)
// The array is incremented, so the same number must be adjacent, and if the number traversed is greater than the target value, then exit. 100% func search2(nums []int, target int) int { count := 0 for _, num := range nums { if num == target { count += 1 } if num > target { break } } return count }Copy the code

Note: This method is recommended, with few lines of code, easy to understand, and high Leetcode score

Method 3: use dichotomy, first find the target value through dichotomy, if found, respectively to the left and right of the target value traversal (because the same value is adjacent), until the target value does not appear

  • Time complexity: O (logN) + 2O (N) ≈ O (N)
  • Space complexity: O (1)
// Time: 6.45% memory: Func search3(nums []int, target int) int {count := 0 tar := binarySearch(nums, Target) if tar == -1 {return count} // for I := tar -1; i >= 0; I -- {if nums[I] == target {count += 1} else {break}} i < len(nums); i++ { if nums[i] == target { count += 1 } else { break } } return count } func binarySearch(nums []int, target int) (index int) { left, right := 0, len(nums)-1 for left <= right { m := (left + right) >> 1 if nums[m] < target { left = m + 1 } else if nums[m] > target {  right = m - 1 } else { return m } } return -1 }Copy the code

Note: This method is not recommended because of the large number of lines of code and the low score of Leetcode

5. Missing digits in [0 ~ n-1] (offer.53_2)

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

Title description:

All numbers in an incrementally sorted array of length n-1 are unique, and each number is in the range 0 to n-1. Find one and only one of the n digits in the range 0 to n-1 that is not in the array. Note: Arrays are incrementedCopy the code

For simple array problems, the first consideration is to iterate over the number group. The rule is to subtract the first number from the second number. If the number is not 1, the number is missing, but there are some special cases as follows:

  • 1. If the first value is not 0, the missing value is 0
  • 2. If the latter minus the former does not equal 1, the missing value is the index of the latter (or the latter minus one)
  • 3. If there is no missing value after the traversal, the missing value is the last number +1
  • Time complexity: O (N)
  • Space complexity: O (1)
// time: 91.08% memory: Int 61.82% func missingNumber1 (nums int []) {/ / the first number is not zero, the missing value of 0 n: = len (nums) if n = = 0 | | nums [0]! For I := 0; for I := 0; for I := 0; i < n-1; i++ { if nums[i+1]-nums[i] ! Return nums[I +1] -1 return I +1}} return nums[n-1] +1} return nums[n-1] +1}Copy the code

Method 2: Since the array is increasing and it is actually an arithmetic sequence, the missing number can be obtained by subtracting the sum of the actual number from the estimated sum of the arithmetic sequence. The estimated sum can be obtained by the arithmetic sequence formula. The sum of the actual number needs to be iterated

  • Time complexity: the complexity of O (N) iterations
  • Space complexity: O (1)
// Time: 91.22% memory: Func missingNumber2(nums []int) int {// Count := 0 for _, Nums := n*0 + (n*(n-1))/2 return s-count}Copy the code

Method three: use dichotomy. Dichotomy makes use of an implicit rule of this problem, that is, the value of the index and the value of the store are equal, if not, it indicates that there is a dislocation.

If the values are equal, the left half interval has no missing, so the next step is to search the right half interval; If the values are not equal, the right half interval is not missing, and the left half interval needs to be searched.

  • Time complexity: O(logN)
  • Space complexity: O(1)
left, right := 0, len(nums)-1 for left < right { mid := (left + right) >> 1 if nums[mid] ! Left = mid + 1} else {// left = mid + 1}} If left == len(nums)-1 && nums[left] == left {return left +1} return leftCopy the code

Note: It seems that Leetcode’s running score is not very accurate, so O(logN) may not be better than O(N)

6. Sum of two numbers (Leet.1)

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

Title description:

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.Copy the code

For simple array problems, first consider violent traversal. Select the first element and then start traversal from the second element until you find two integers with and as the target values.

  • Time complexity: O (N2)
  • Space complexity: O (1)
Func twoSum1(nums []int, target int) []int {n := len(nums) for I := 0; i < n-1; i++ { for j := i + 1; j < n; j++ { if nums[i]+nums[j] == target { return []int{i, j} } } } return []int{} }Copy the code

Method two: Use hash tables. We can set the two numbers to be searched as A and B, and set the target value as C. We can get A+B=C, that is, B= c-a, where A is the traversal value, B is the value to be matched, and C is the target value.

At this time, we iterate over the number group, we use the hash table key to store the value of B, value stores the index of B, if the value to be searched exists in the hash table, return; If not, the current value and its index are put into the hash table.

  • Time complexity: O (n)
  • Space complexity: O (n)
// time: 96.99% memory: Func twoSum2(numS []int, target int) []int {// key is a value, value is a subscript diffMap := map[int]int{} for I := 0; i < len(nums); i++ { a := nums[i] b := target - a if _, ok := diffMap[b]; Return []int{I, diffMap[b]} diffMap[a] = I} return []int{}}Copy the code

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

Article Leetcode array (on) | August more challenges