01. Duplicate number in array

  • Topic describes

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.

  • Their thinking

Each time a new nums[I] with index I is encountered, it is swapped to nums[nums[I]] with index nums[I]. When traversal encounters a repeated number x, there must be nums[x] == x (because x was swapped to nums[x] when it was first encountered). Using the above method, a set of repeated numbers can be obtained.

  • Code implementation
Let findRepeatNumber = function(nums) {let findRepeatNumber = function(nums) { While (I < nums.length){// nums[I] == I if(nums[I] == I){I ++; continue; } nums[I] == nums[I] if(nums[I]] == nums[I]) return nums[I]; Let TMP = nums[I]; let TMP = nums[I]; nums[i] = nums[tmp]; nums[tmp] = tmp; } // If no return is returned after traversal, -1 is returned, indicating that the array does not have the same value return-1; }; // The time complexity is O(N), the traversal number group uses O(N), and the judgment and swap operation of each round uses O(1). // The space complexity is O(1), using extra space of constant complexity.Copy the code

02, A search in a two-dimensional array

  • Topic describes

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. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

  • Their thinking

If the matrix is traversed by violence, the time complexity is O(MN). The violence method does not take advantage of the feature of matrix “increasing from top to bottom and from left to right”, so it is obviously not the optimal solution. In this problem, token number is introduced with matrix characteristics, and the time complexity of the algorithm is reduced by token number properties.

  • Code implementation
Let findNumberIn2DArray = function(matrix, target) { Let I = matrix. Length-1; let j = 0; While (I >= 0 &&j < matrix[0].length){// If (matrix[I][j] > target) I --; If (matrix[I][j] < target) else if(matrix[I][j] < target) j++; // Matrix [I][j] == target, return true else return true; } // If the row index or column index is out of bounds, there is no target value in the matrix. Return false; }; // Time complexity O(M+N), where N and M are the number of rows and columns of the matrix respectively, this algorithm can loop M+N times at most. // Space complexity O(1), Pointers I, j use constant size extra space.Copy the code