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!