[C language brush questions] Double pointers modify the array in place (analysis of the original title)

Hits: 0

Article directory

Double pointers modify the [array] in place (analysis of the original title)

Question 1: Leetcode27 – Remove Elements

Topic description

Given an array nums and a value val, you need to remove all elements whose value is equal to val in place, and return the new length of the removed array.
Don’t use the extra array space, you have to use only O(1) extra space and modify the input array in-place.
The order of elements can be changed. You don’t need to consider elements in the array beyond the new length.

Link : Leetcode27

Example

Example 1:
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2]
Explanation:
The function should return a new length of 2, and the first two elements in nums are both is 2. You don’t need to consider elements in the array beyond the new length. For example, the new length returned by the function is 2, and nums = [2,2,3,3] or nums = [2,2,0,0] would also be considered the correct answer.

Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3]
Explanation: The
function should return The new length is 5, and the first five elements in nums are 0, 1, 3, 0, 4. Note that these five elements can be in any order. You don’t need to consider elements in the array beyond the new length.

hint

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

core code pattern

int removeElement(int* nums, int numsSize, int val)
{

}

Thought analysis and code implementation (C language)

1. Double pointer in-place modification method

Define two subscripts src and dst. Hey, this is not a pointer, is it a lie? No, using array subscripts is no different from using pointers in terms of logic. src traverses the array, dst is used for “sealing”, that is, src is used to detect whether the element is val, if not, there is no need to remove it, then put it in the sub-array managed by dst, and then dst is incremented by 1, which looks like Isn’t it like src is loading cargo into bags? dst is the mouth of the bag. It is finished when there is nothing left, and dst is used to “seal”.
It is equivalent to using dst to create a sub-array in an array to store the elements that are not deleted, and finally just print this sub-array.
This is an operation performed on the original array, without additionally opening up other arrays, and the space complexity is O(1), that is, modifying the contents of the array in place.

2. (Not applicable to this question) Auxiliary array double pointer method

Create two arrays of equal size, one to store the original sequence of the input and the other to store the sequence with the specified numbers removed. This idea does not consider the sequence order, directly traverses the original sequence array, and compares the numbers to be deleted one by one. If it is the target number, it will continue to loop. If it is not the target number, it will be put into the new sequence array in subscript order. Finally output the new sequence array. In this way, there is no need to find the target number specially, the array transplantation can be completed by a loop traversal, and the number to be deleted will not be put into a new array, and the requirements are simply and clearly completed.
Create an additional auxiliary array that is the same size as the original array, define the subscript src to correspond to the original array, and dst to correspond to the auxiliary array. As long as src does not “go” to the end of the original array, it will continue to loop, and the last src of each cycle will increment by 1. Move, in the loop, if the element encountered by src is different from val, the element is put into the auxiliary array, and dst is incremented by 1 to move backward. If the element encountered by src is the same as val, do nothing, src Find the next element. In this way, the elements that do not need to be removed are all placed in the auxiliary array in the original order, and the elements to be removed are not placed. Finally, copy the elements of the auxiliary array to the original array.

Question 2: Leetcode26 – Removing Duplicates in an Ordered Array ### The title description gives you an array nums in ascending order, please situ delete the duplicate elements so that each element occurs only once, returns the new length of the deleted array. The relative order of elements should remain consistent. Since the length of the array cannot be changed in some languages, the result must be placed in the first part of the array nums. More canonically, if there are k elements after removing duplicates, then the first k elements of nums should hold the final result. Returns k after inserting the final result into the first k positions of nums. Don’t use the extra space, you have to modify the input array in-place and do it with O(1)** extra space.

Link : [Leetcode26]

Example

Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2]
Explanation:
The function should return a new length of 2, and the first two elements of the original array nums are modified to 1, 2 . Elements in the array beyond the new length need not be considered.

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4]
Explanation: The
function should return The new length is 5, and the first five elements of the original array nums are modified to 0, 1, 2, 3, 4. Elements in the array beyond the new length need not be considered.

hint

  • 1 <= nums.length <= 3 * 104
  • -104<= nums[i] <= 104
  • nums are sorted in ascending order

core code pattern

int removeDuplicates(int* nums, int numsSize)
{

}

Thought analysis and code implementation (C language)

Two-pointer in-place modification method

In fact, the idea is very similar to the previous question. We still define two subscripts, src corresponds to the original array, dst corresponds to the sub-array, or traverse the array once, but the judgment condition of this question needs to be changed-judging the src encountered Whether the element is the same as the element corresponding to dst, if it is the same, don’t skip it directly, and only put it into the sub-array managed by dst when it encounters a different one, until the original array is accessed by src. However, it should be noted that when src encounters different elements, dst must be incremented by 1 first, and then nums[src] is assigned to nums[dst]. dst points directly to the last element of the subarray (this is the same as the previous one). The question is different), so let dst add 1 to the final return value.

Question 3: Leetcode88 – Merge Two Sorted Arrays

Topic description

You are given two integer arrays nums1 and nums2 in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2, respectively.
Please merge nums2 into nums1 so that the merged arrays are also arranged in non- decreasing order .
Note : Ultimately, the merged array should not be returned by the function, but stored in the array nums1. To cope with this situation, nums1 has an initial length of m + n , where the first m elements represent elements that should be merged, and the last n elements are 0 and should be ignored. The length of nums2 is n.

Link : [Leetcode88]

Example

Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5 ,6]
Explanation:
Need to combine [1,2,3] and [2,5,6]. The combined result is [1,2,2,3,5,6], where the elements in nums1 are marked in bold italics.

Example 2:
Input: nums1 = [1], m = 1, nums2 = [ ], n = 0 Output: [1]
Explanation:
Need to combine [1] and [ ]. The combined result is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1]
Explanation:
The arrays to be merged are [] and [1]. The combined result is [1]. Note that since m = 0, there are no elements in nums1. The only 0 in nums1 is to ensure that the merged result can be stored in nums1 smoothly.

hint

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

Advanced
Can you design and implement an O(m + n) algorithm to solve this problem?

core code pattern

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{

}

Thought analysis and code implementation (C language)

Multi-pointer in-place modification method

Hey, isn’t it a double-pointer, how did it become a multi-pointer? This problem is a bit special. If only two pointers are used, it may be more troublesome. We design an additional auxiliary pointer and use reverse thinking to efficiently solve this problem.
In fact, this question has an idea of ​​​​using space for time . You can open up an auxiliary array, and then use two subscripts to point to the two arrays nums1 and nums2 respectively, and compare the size of the elements of the two arrays in the order from front to back. , the small ones are put into the auxiliary array first, and the larger ones continue to be compared with the following elements. When all the elements are moved, the auxiliary array elements are copied to the nums1 array, so that the space complexity is O(m+n) , is there a more space-saving way, that is, can it be modified in place?
If we refer to the idea of ​​​​changing space for time to modify it in situ, and compare the element sizes of the two arrays from front to back, it may cause elements to cover lost elements. For example, nums1 is 1, 2, 5and nums2 is 3, 3, 4, it will make The first 3 in nums2 overwrites the 5 in nums1. So, we have to find another way.
Then we might as well think backwards. Since it will be covered from the front to the back, what about from the back to the front ?
Define two subscripts p1 and p2, corresponding to the arrays nums1 and nums2 respectively, and define a subscript cur starting from the end of nums1, and moving forward one place each time an element is placed, while p1 and p2 start from the end of the two arrays Start with the valid element of , move forward, compare the size of the elements of the two arrays, pay attention, here is to take out the larger one and put it at the position pointed to by cur.
However, moving to the back will reveal that there are two cases :
Case 1The elements of the array nums2 are moved first, and the whole process can end at this time, as shown in the figure:

You may also like...

Leave a Reply

Your email address will not be published.