This is the 15th day of my participation in the August More Text Challenge

Reference to duplicate number in Offer 03 array

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.

Input: [2, 3, 1, 0, 2, 5, 3] Output: 2 or 3Copy the code

Limitations:

2 <= n <= 100000

Answer key

Method one hash table

We can use hash table to realize the problem. Analysis is as follows:

  1. Iterate over the number group, if the current number does not exist in the hash table, then add to the hash table.
  2. Returns the result if it already exists in the current numeric hash table.
 var findRepeatNumber = function(nums){
   let map = new Map(a);for(let i of nums){
     if(map.has(i)){
       return i;
     }
     map.set(i,1);
   }
   return null;
 }
Copy the code

  • Space complexity: O(n)

  • Time complexity: O(n)

Alpha two are exchanged in place

Solution in reference to Offer, space complexity O(1) time complexity O(n)

Because all the numbers in a numS of length N are in the range 0 to n-1, the index and value of the array elements are one-to-many. Therefore, the mapping between the index and value can be established to play the role of dictionary equivalence.

Ideas:

  1. Scan from beginning to end. If the current item is not equal to the subscript, compare the current item with the subscript corresponding to the current item. If the current item is not equal, swap places
  2. The for loop has a while, but since each item is swapped at most twice in the while, the overall time complexity is still O(n).
 var findRepeatNumber = function(nums) {
     for(let i = 0; i < nums.length; i++){let num = nums[i];
       while(num ! == i){if(nums[i] === nums[num]){
           return num
         }
         nums[i] = nums[num]
         nums[num] = num
       }
     }
   return null
 };
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)

Reference to Offer 04. Search in a two-dimensional array

Lookup in a two-dimensional array

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.

🌰 The existing matrix is as follows:

[[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]Copy the code

Given target = 5, return true; Given target=20, return false.

Limit: 0 <= n <= 1000; 0 <= m <= 1000

Answer key

Method of coordinate axes

The two-dimensional array increases from left to right and from top to bottom, then:

  • Any number in a column, any number above that number, is less than that;
  • Any number in a row, any number to the right of that number, is greater than that number;

Therefore, the problem solving process is as follows:

  1. Using the lower left corner of the two-dimensional array as the origin, the rectangular axes are established.
  2. If the current number is greater than the search number, the search moves up one bit.
  3. If the current number is less than the search tree, the search is moved one bit to the right.

If target = 19, the path is 18->21->13->14->17->24->22->19

 var findNumberIn2DArray = function(matrix,target){
   if(! matrix.length)return false;
   let x = matrix.length-1 , y = 0;
   while(x>=0 && y< matrix[0].length){
     if(matrix[x][y] === target){
       return true;
     }else if(matrix[x][y] > target){
       x--;
     }else{ y++; }}return false;
 }
Copy the code

Method two array dimension reduction

Flatten the two-dimensional array to see if it contains the target value.

 var findNumberIn2DArray = function(matrix,target){
   return matrix.flat(Infinity).includes(target);
 }
Copy the code