preface
This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge
Hello, everyone, I also become a member of the brush army, this Leetcode array is divided into three pieces, this is the next, and the first and the middle.
For each topic, I will specify the topic link, topic description, and whether it belongs to “Sword Point Offer” or Leetcode question bank, so that you can check it out and watch it.
In addition, I will try my best to provide a variety of solutions for each problem, the understanding of each solution will be from simple to difficult, if you just brush to this problem, I hope to help you!
Finally, it is suggested that the same type of questions brush together, so that you can probably explore the common routine of the problem, do it more efficient!
Note: All code in this article is implemented in Golang language
7. Find the median of the two ordinal groups (Leet.4)
Title link: leetcode-cn.com/problems/me…
Topic Description:
Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of these two ordinal groups. Advanced: Can you design an algorithm of order log (m+n) to solve this problem?Copy the codeThe median, the number in the middle, is the number that’s bigger for half of the data set and smaller for half of the data set
答 案 :
Method 1: Method 1 is the simple idea of merging two arrays and reordering them (or sorting them as they are being merged) to get the median
- Time complexity: O (n + m)
- Space complexity: O (n + m)
// Method 1: first merge, then find the median
// time: 44.09% memory: 6.85%
func findMedianSortedArrays1(nums1 []int, nums2 []int) float64 {
// Merge the array first, and sort it incidentally during the merge
merge := []int{}
n1, n2 := len(nums1), len(nums2)
point1, point2 := 0.0
for n1 > point1 && n2 > point2 {
if nums1[point1] < nums2[point2] {
merge = append(merge, nums1[point1])
point1 += 1
} else {
merge = append(merge, nums2[point2])
point2 += 1}}// If nums1 is merged first, then nums2 is merged (because nums1 and nums2 are both positive)
if n1 <= point1 {
merge = append(merge, nums2[point2: n2]...)
}else{
// If nums2 is merged first, the remaining nums1 is merged
merge = append(merge, nums1[point1: n1]...)
}
return calMedium(merge)
}
// Calculate the median
func calMedium(nums []int) float64 {
count := len(nums)
if count%2= =1 {
return float64(nums[count/2])}else {
return (float64(nums[count/2]) + float64(nums[count/2- 1) /])2}}Copy the codeMethod 2: Method 2 is an optimization of method 1, in fact, we don’t need to merge the array to know the median, when we know the length of the two arrays, we already know where the median is, and the advantage of this method is that it saves memory.
- Time complexity: O (n + m)
- Space complexity: O (1)
// Method 2: use Pointers instead of arrays to save memory
// Time: 43.52% memory: 77.48%
func findMedianSortedArrays2(nums1 []int, nums2 []int) float64 {
n := len(nums1)
m := len(nums2)
total := n + m
// Point1 and point2 represent two Pointers to the array
point1, point2 := 0.0
/ / prev, next respectively on a value, and the next value, because if the array length sum for an even number, need to use the sum of two Numbers in the middle
prev, next := - 1.- 1
// We need to iterate over total/2+1 times whether the sum of two arrays is odd or even
for i := 0; i <= total/2; i++ {
prev = next
if point1 < n && (point2 >= m || nums1[point1] < nums2[point2]) {
next = nums1[point1]
point1 += 1
} else {
next = nums2[point2]
point2 += 1}}/ / the number
if total%2= =0 {
return float64(prev+next) / 2
} else {
return float64(next)
}
}
Copy the codeThe above code needs a few points of clarification:
- 1. Why traversal
total/2 + 1Times? Let’s say totalThe length of the merged arrayIf it is odd, we need to know the (total+1) /2 number; If it’s even, we need to know the number total/2 and total/2+1, and we also need to iterate over total/2+1. So whether it’s odd or even, we’re traversing ittotal/2+1Times. - 2. Why do we need a prev pointer? As mentioned in the code comment above, since the combined array is even in length, we need to use the middle two numbers to calculate the median, so we need to add a prev pointer to store the previous value
- About 3.
point1 < n && (point2 >= m || nums1[point1] < nums2[point2])Nums1 or nums2 is not necessarily longer than total/2 + 1, so there is a possibility that the array will be out of bounds.
Method 3: The time complexity of the above two algorithms is O(n + m), but neither of them can meet the advanced requirement of this problem: O(log (m+n)). When we encounter the sorted array and the time complexity requirement is log, we can easily think of dichotomy.
So the other way to think about it, is that finding the median is actually the KTH smallest number, is the same thing as finding the KTH smallest number in the combined array. See the solution here for details
- Time complexity: O(log (m+n))
- Space complexity: O (1)
// Method 3: binary search, order generally needs to consider binary
// Method 2 drops the non-median values one by one by traversal method, and method 3 drops the non-median values by binary method
// Time: 98.72% memory: 78.26%
func findMedianSortedArrays3(nums1 []int, nums2 []int) float64 {
n := len(nums1)
m := len(nums2)
// Combine the even and odd cases. If it is odd, the same k will be found twice
// When n+m is even, for example, 14, left=7, right=8, we want the 7th and 8th smallest values, the sum divided by 2 is exactly the median
// When n+m is odd, for example, 15, left=8, right=8
left := (n + m + 1) / 2
right := (n + m + 2) / 2
return float64(getKth(nums1, 0, n- 1, nums2, 0, m- 1, left)+getKth(nums1, 0, n- 1, nums2, 0, m- 1, right)) / 2
}
/ /!!!!!! Get the KTH smallest number!!
func getKth(nums1 []int, start1, end1 int, nums2 []int, start2, end2 int, k int) int {
// The current length of len1 and Len2 arrays after each iteration, since each iteration excludes non-median values
len1 := end1 - start1 + 1
len2 := end2 - start2 + 1
// Make len1 less than len2, so that if there is an empty array, it must be len1
if len1 > len2 {
return getKth(nums2, start2, end2, nums1, start1, end1, k)
}
// When nums1 is empty, there is no need to continue searching. In this case, the KTH smallest number is only needed to search nums2
// start2 is the current index, k-1 is because the index starts from 0
if len1 == 0 {
return nums2[start2+k- 1]}// K will be divided by 2 in each iteration, so k will end up equal to 1 (or some array will be empty)
// When k=1, that is, to find the first smallest number, just compare nums1 with the first number of nums2 (nums1 and nums2).
if k == 1 {
return min(nums1[start1], nums2[start2])
}
// K /2 May be larger than the array length, so keep it to a minimum
i := start1 + min(len1, k/2) - 1
j := start2 + min(len2, k/2) - 1
if nums1[i] > nums2[j] {
// If the value of array 1 is greater than that of array 2, then array 2 does not have the required number of j's before it, so start becomes j+1
// j-start2+1 indicates the length of exclusion, so k-(j-start2+1) gives the latest k
return getKth(nums1, start1, end1, nums2, j+1, end2, k-(j-start2+1))}else {
return getKth(nums1, i+1, end1, nums2, start2, end2, k-(i-start1+1))}}func min(a, b int) int {
if a < b {
return a
}
return b
}
Copy the codeNote: The above code is rewritten with Go according to the solution of Leetcode, and added with your own understanding
8. The container that holds the most water (Leet.11)
Title link: leetcode-cn.com/problems/co…
Topic Description:
I give you n non-negative integers A1, A2... Each number represents a point (I, ai) in the coordinates. Draw n vertical lines in the coordinates, and the two ends of the vertical line I are (I, ai) and (I,0). Find two of these lines so that they, together with the X-axis, can hold the most water in the container. Note: You cannot tilt a container.Copy the code
Method 1: At first, the idea was how to find two pillars with the longest distance and high height, but on second thought, this idea is actually not quite right, and it is also difficult for the machine to achieve.
So this problem can be translated into finding two numbers that have the highest capacity, so the easiest way to do this is to brute force iterate, which is to iterate through a two-dimensional array and store the maximum capacity in one variable.
- Time complexity: O (n2)
- Space complexity: O (1)
// Method 1: violent traversal
// time/memory: time limit exceeded
func maxArea1(height []int) int {
max := 0
for i := 0; i < len(height)- 1; i++ {
for k := i + 1; k < len(height); k++ {
area := (k - i) * getMin(height[i], height[k])
if area >= max {
max = area
}
}
}
return max
}
func getMin(a, b int) int {
if a > b {
return b
}
return a
}
Copy the codeNote: the above code cannot be passed in Leetcode, because the time limit is exceeded, so for reference only!!
Method 2: Use double Pointers. Double pointer refers to the definition of two left and right Pointers and the use of a variable to store the maximum capacity. Taking the above question array as an example, after the first round of calculation, the capacity is min(1, 7) * 8 = 8. In the second round of calculation, we need to move a column. Since the capacity is determined by the low height column, we need to move the left column (pointer) and calculate the capacity again, and so on. When the left and right Pointers overlap (equal), the calculation stops.
- Time complexity: O (n)
- Space complexity: O (1)
// Method 2: double pointer
Memory: / / time: 89.15% to 30.09%
func maxArea2(height []int) int {
left := 0
right := len(height) - 1
area := 0
for left < right {
tmp := getMin(height[left], height[right]) * (right - left)
area = getMax(tmp, area)
if height[left] > height[right] {
right -= 1
} else {
left += 1}}return area
}
func getMin(a, b int) int {
if a > b {
return b
}
return a
}
func getMax(a, b int) int {
if a > b {
return a
}
return b
}
Copy the codeNote: the solution of double pointer is very simple, but the difficulty of this problem is why the solution of double pointer is right, will not miss some cases?
In the first round of calculation, if the left pointer height is x and the width of the container is t, no matter how the right pointer moves, the capacity will not exceed x * t. In the second round of calculation, we need to move a column. Since the left pointer is smaller than the right pointer, the left pointer must be moved. In the second round of calculation, we will not use the first column, which can be regarded as discarded.
So each round we can actually get rid of one column, reducing the size of our array and doing the same thing the next round.
9. The sum of three numbers (Leet.15)
Title link: leetcode-cn.com/problems/3s…
Topic Description:
Given an array of n integers, nums, determine if there are three elements a, b, and c in NUMs such that a + b + c = 0? Find all triples that sum 0 and are not repeated. Note: Answers may not contain duplicate triples.Copy the codeMethod 1: Sort + double pointer. The specific steps of this method are as follows:
- 1. Check whether the length of the array is less than 3
- 2. Sort the array to facilitate subsequent judgment and remove repeated solutions
- 3. Iterate the array, and use double pointer to solve the remaining part of the array to meet the condition of triple
How do you remove duplication? To get rid of duplicate triples, you just have to satisfy that two neighboring numbers are not equal. Take the array [0, 1,2,2,2,3] as an example. If we use a triple loop, we can get the triplet (0,1,2) at the beginning, but because the next 2 repeats, there will be a repetition, so we need to skip to the next different number, which is 3, to get the triplet (0,1,3).
You can see the detailed solution here
- Time complexity: O (n2). Array sorting O(N logn), traversing the array O(N), double pointer traversing O(N), the overall complexity is O(N logn) + O(N) * O(N) = O(n2).
- Space complexity: O (1)
// Method 1: sort + double pointer
// time: 97.10% memory: 71.82%
func threeSum1(nums []int)[] []int {
res := [][]int{}
n := len(nums)
// If the length of the array is less than 3, the array cannot be returned
if n < 3 {
return res
}
// Sort the array for easy judgment and easy search
sort.Ints(nums)
for i := 0; i < n; i++ {
// If the first value of the array is greater than 0, all the other values will be greater than 0
if nums[i] > 0 {
return res
}
// Remove the repeated solution. If two adjacent numbers are equal, there will be a repeated solution
// n > 0 is used to avoid array overbounding
if i > 0 && nums[i] == nums[i- 1] {
continue
}
A +b+c=0; a+b+c=0;
left := i + 1
right := n - 1
for left < right {
if nums[i]+nums[left]+nums[right] == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
// If adjacent values are equal, i.e. there are repeated solutions, skip to the next unequal number
// It is possible to repeat more than one value, such as [0, 1, 2, 2, 3], so a while loop is needed
for left < right && nums[left] == nums[left+1] {
left += 1
}
// For the same reason, remove repeated solutions
for left < right && nums[right] == nums[right- 1] {
right -= 1
}
left += 1
right -= 1
} else if nums[i]+nums[left]+nums[right] > 0 {
// If the sum is greater than 0, nums[right] is too large and needs to be moved to the left
right -= 1
} else {
left += 1}}}return res
}
Copy the codeArray Summary
This is the end of the array section. At the beginning, I mentioned that I suggested the same type of questions to brush together, so as to explore the common routines of this kind of questions, after brushing these nine questions, I also have some experience to share with you, I hope to help you!
I personally divide the common solutions to arrays into several categories: traversal, sorting, space for time, dichotomy, and double pointer.
Traversing method: in fact, it is traversing the number group, which is simple and rough, and can solve most problems. The disadvantage is that the time complexity is high, and sometimes it may not meet the requirements of the problem. For example, the eighth question (the container with the most water), the violent traversing will time out.
Sorting method: I think the array problem, need to have the sense of sorting, sometimes through sorting, the whole problem will become much simpler, such as the ninth problem. And sorting is often paired with traversal, dichotomy, and so on, as an auxiliary means.
Space-for-time method: Space-for-time method is actually a way to reduce the time complexity through arrays, hash tables and other storage structures. Typical example is to find the repeated numbers in the array of Leetcode (above).
Dichotomy: encounter array search, especially the sorted array, dichotomy is almost indispensable, the principle of dichotomy is relatively simple, but also can reach the complexity of logN. But dichotomies can be tricky, like in problem 7 above, finding the median.
Double pointer method: double pointer is a method of brush problem since these days to learn, through the use of end pointer (or pointer), as well as in the title of hidden rules (positive sequence, equal to zero, etc.), can be reduced the complexity of O (n2) to O (n), is a kind of with dichotomy are equally important, the method of typical questions such as the eighth and ninth items.
Write in the last
If there are any mistakes in this article, please point them out in the comment section, and thank you very much. In addition, if this article is useful to you, please also ask guests to point a little love 💖!
Other articles
Article Leetcode array (on) | August more challenge Leetcode array in August (in the) | article more challenges