This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

August has passed half, this half month only one day is sleep before 2 o ‘clock in the morning, write the article more and more addictive, the previous notes are sorted out, their review again, but also to help others, good ah

But today at work to receive a lot of demand, good helpless, so this week will be relatively busy, no time to write the article when the brush algorithm problem

Hope you are the same, usually have time to brush questions on LeetCode, accumulated up to improve really great, especially now a little better factory interview will test algorithm, we have no reason not to work hard

Let’s start today’s problem

Repeated number in an array

Here’s the title:

All numbers in an array of length n, nums, are in the range 0 to n-1. Some of the numbers in the array are repeated, but it is not known how many of them are repeated or how many times each number is repeated. Please find any duplicate number in the array

Example:

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

Limitations:

2 <= n <= 100000
Copy the code

O(n^2) brute force

So that makes sense, just write a function, pass an array in, and then return the repeated value in the array, and then return the first repeated value. Easy

function findRepeatNumber(nums) {
    for(let i = 0; i < nums.length; i++){
        for(let j = 0; j < nums.length; j++){
            if(nums[i] == nums[j]){
                return nums[i]
            }
        }
    }
    return -1
}
let reqeatNum = findRepeatNumber([2.3.1.0.2.5.3])
console.log( reqeatNum ) / / 2
Copy the code

Got it, hahaha

To really write so can be finished, so brute force cracking, not only won’t add points, I’m afraid will deduct points, and such a code to write out, I’m afraid will be laughed at

Because of the nested loop, the efficiency is reduced exponentially, because the time complexity is so high, so the time complexity of the two-level loop is O(n^2). If it’s one level of loop, let’s say the array is 10 times long, that’s 10 times, but if we nested another level of loop, that’s 10 x 10 = 100 times, which is horrible, so let’s think about how we can reduce the number of nested loops to make it more efficient,

O(n)

So let’s reorganize our thinking, how do we reduce the time complexity to order n?

Save each value of each loop into a hash table, using the non-repeatability of the object’s key name, if you find some key names in the object, it is repeated, and then return

Look at the code

function findRepeatNumber(nums) {
    let obj = {}
    for(let i = 0; i < nums.length; i++){
        if(obj[nums[i]]){
            return nums[i]
        }
        obj[nums[i]] = true
    }
    return -1
}
let reqeatNum = findRepeatNumber([2.3.1.0.2.5.3])
console.log( reqeatNum ) / / 2
Copy the code

Or ES6 Map is the same thing

function findRepeatNumber(nums) {
    let map = new Map(a)for(let i = 0; i < nums.length; i++){
        if(map.has(nums[i])){
            return nums[i]
        }
        map.set(nums[i], true)}return -1
}
let reqeatNum = findRepeatNumber([2.3.1.0.2.5.3])
console.log( reqeatNum ) / / 2
Copy the code

So this is going to help us reduce one layer of nested loops, so it’s going to be much more efficient, and the complexity of the algorithm has gone from O(n^2) to O(n).

A lookup in a two-dimensional array

Here’s the title:

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 an efficient function that inputs such a two-dimensional array and an integer and determines whether the array contains the integer

The sample

Now the matrix matrix looks like this:

let arr = [
  [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

Return true if target = 5

Return false for target = 20

limit

0 <= n <= 1000

0 <= m <= 1000
Copy the code

O(n^m) brute force

Old rule, brute force cracking is not a look to have a train of thought, hahaha

function findNumberIn2DArray(matrix, target) {
    for(let i = 0 ; i < matrix.length ; i ++){
        for(let j = 0 ; j < matrix[0].length ; j ++){
            if(matrix[i][j] == target){
                return true; }}}return false;
}
let findNum1 = findRepeatNumber( arr, 5 )
let findNum2 = findRepeatNumber( arr, 20 )
console.log( findNum1 ) // true
console.log( findNum1 ) // false
Copy the code

I’m not going to repeat the reasons, so this still doesn’t work

Think about it, how can I reduce the number of cycles?

Order n plus m linear search

Let’s look at a given array of matrices, and one of the things that happens is that each row is increasing from left to right, and each column is increasing from top to bottom. Let’s look at the graph

If it is larger than target, go to the left. If it is smaller than target, go to the right. This will reduce the number of times to find the target in half

So it’s going to be

Take the element in the upper right corner of the matrix as the root, and look from there if the element is larger than target, move it to the left column and if the element is smaller than target, move it to the bottom row

If you don’t understand, pause to understand

To the problem solving

let arr = [
  [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]]function findNumberIn2DArray(matrix, target) {
    let rows = matrix.length, / / the total number of rows
        columns = matrix[0].length, // Array length
        row = 0, 
        column = columns - 1 // The subscript of the root
    while (row < rows && column >= 0) {
        let num = matrix[row][column] // Fetch the root value
        if (num == target) return true // The root value is equal to the target value
        else if (num > target) column-- // If the root value is greater than the target value, skip the current column, move one column to the left, and continue searching
        else row++ // If the root value is less than the target value, skip the current column and move down one row to continue the search
    }
    return false
}
let findNum1 = findRepeatNumber( arr, 5 )
let findNum2 = findRepeatNumber( arr, 20 )
console.log( findNum1 ) // true
console.log( findNum1 ) // false
Copy the code

If you don’t understand, the graph above, pause to understand

So that’s the end of the problem

conclusion

Praise support, hand stay fragrance, and have glory yan

Thank you for seeing this!