I have a new experience, that is, do not think of pass to complete, have to think of ways to increase their running time
Take LeetCode 565 for example. An integer array A of length N, with each number in the range 0 to n-1, is assumed to start from some index I of the array and perform A[I] evaluation successively, adding the resulting numbers to the set S until there are duplicate elements in the set S, i.e. abort the operation. For example, if the array [5,4,0,3,1,6,2] is evaluated from 0, we have:
A[0]=5 -> A[5]=6 ->
A[6]=2 -> A[2]=0
-x-> A[0]=5
Copy the codeIn the previous example our S set was {5,6,2,0}. Now given an array, we want to find the maximum length of the set.
Iterate over each value of the array, take index I as the starting point and execute A[I] (count the current number of operations), terminate when an evaluation operation is the same as the starting point I, and finally take the maximum value, the corresponding code is as follows
func arrayNesting(nums []int) int {
n := len(nums)
if n <= 1 {
return 1
}
result := 0
for i := 0; i < n; i++ {
s, current, tmpl := i, nums[i], 1
forcurrent ! = s { current = nums[current] tmpl++ } result = maxValue(result, tmpl) }return result
}
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
Copy the codeThis code also passed, but the time is still very unfriendly, unexpectedly at the level of thousand milliseconds
If you think about it later, using the original array [5,4,0,3,1,6,2], starting from index 0 gives you [5,6,2,0], whereas essentially starting from index 2, 5, or 6 gives you the same set, because they always form a ring. In this case, we can ** set a Boolean array and determine that the current value does not need to be re-evaluated if it has already appeared in set S
func arrayNesting(nums []int) int {
n := len(nums)
if n <= 1 {
return 1
}
visited := []bool{}
for i := 0; i < n; i++ {
visited = append(visited, false)
}
result := 1
for i := 0; i < n; i++ {
s, current, tmpl := i, nums[i], 1
visited[s] = true
if visited[current] {
continue
}
forcurrent ! = s { current = nums[current] visited[current] =true
tmpl++
}
result = maxValue(result, tmpl)
}
return result
}
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
Copy the codeThe result is that the running time is much better than before, just 20 milliseconds
Given a two-dimensional array of m*n, it is ordered from left to right and from top to bottom, as shown below:
[[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 codeNow let’s do a quick search for a value in this matrix, return true if you find it, false if you don’t, true if you search for 5 and false if you search for 20 in this example
First of all, the most intuitive thinking is to traverse each row of the matrix and determine whether the current value is between the 0th element of the current row and the last element. If so, do a binary search of the array of the current row
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
if m == 0 {
return false
}
n := len(matrix[0])
if n == 0 {
return false
}
result := false
for _, row := range matrix {
if target >= row[0] && target <= row[n- 1] {
result = binarySearch(row, n, target)
}
if result == true {
return true}}return false
}
func binarySearch(row []int, n, target int) bool {
left, right := 0, n- 1
for left <= right {
m := left + (right-left)/2
if row[m] == target {
return true
} else if target < row[m] {
right = m - 1
} else {
left = m + 1}}return false
}
Copy the codeAlthough this effect can pass and the time is not slow, the running time ranking of this problem only exceeds 31.25% golang coder, which indicates that O(m*log2(n)) is not the optimal time complexity of this algorithm. In addition, in theory, m must be less than n to be considered a good algorithm, so in fact, the solution I just proposed also ignores the classification discussion: traversal by line when m < n, traversal by column when m > n
Like my original idea above, it’s essentially just using left-to-right order, and not taking full advantage of top-to-bottom order. So from that point of view, how can we use both of these properties together to speed things up?
Again, if I want to search for 6, I can start with the number 15 at the top right corner, because 15 is at the top right corner, and because of matrix properties, everything to the left of 15 is smaller than 15 (for rows), and everything below 15 is larger than 15 (for columns).
[
[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 codeThen 6 is less than 15, which means 6 cannot be in the same column as 15, so the range of our array becomes:
[
[1, 4, 7, 11]<-
[2, 5, 8, 12]
[3, 6, 9, 16]
[10, 13, 14, 17]
[18, 21, 23, 26]
]
Copy the codeSimilarly, 6 is smaller than 11 and 7, so the search range of the array is:
[[1, 4, 7] < - [2, 5, 8], [3, 6, 9] [10, 13, 14] [18, 21, 23]] [[1, 4] < - [2, 5] [3, 6] [10, 13] [18, 21]]Copy the codeLooking at the number in the upper right corner, this time 6 is larger than either 4 or 5, which means 6 can’t walk with 4 or 5, so the search is narrowed down to:
[
[2, 5]<-
[3, 6]
[10, 13]
[18, 21]
]
[
[3, 6]<-
[10, 13]
[18, 21]
]
Copy the codeNow that we have 6, we can see that the time complexity of this algorithm is order m plus n at worst, which is a little bit better than before
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
if m == 0 {
return false
}
n := len(matrix[0])
if n == 0 {
return false
}
rightUp, currentRow, currentColumn := - 1.0, n- 1
for currentRow >= 0 && currentRow < m
&& currentColumn >= 0 && currentColumn < n {
rightUp = matrix[currentRow][currentColumn]
if rightUp == target {
return true
} else if rightUp > target {
currentColumn--
} else {
currentRow++
}
}
return false
}
Copy the codeAfter submitting it, the running time was fine
