Remove all elements with value equal to val in place
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 array after removal. Requirement: Do not use extra array space, you must 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.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Two solutions:
The first is the fast and slow dual pointers
Define the slow pointer and the fast pointer so that the fast pointer keeps moving backward. If the value pointed by the fast pointer is not equal to val in the current loop, the value pointed by the fast pointer will be copied to the value pointed by the current slow pointer, and the slow pointer will move to Move one space later. When the value pointed by the fast pointer is val, stop moving the slow pointer and continue to move the fast pointer.
In general, the fast pointer keeps traversing backward, and then the role of the slow pointer is to represent all the values before slow, none of which have val. It is similar to deleting the val value before slow, and finally returning the slow pointer.
public static int removeElement(int[] nums, int val) {
int slow = 0;
//fast acts as a fast pointer
for (int fast = 0; fast < nums.length; fast + + ) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow + + ;
}
}
//The number of remaining elements at the end
return slow;
}
The second method is the two-pointer collision method
The double-pointer collision method means that double pointers are still defined, but the usage is changed based on the above.
First, the slow and fast pointers are still defined, but the slow pointer points from the front, while the fast pointer points from the back.
The slow pointer keeps moving backward. When the value pointed by the slow pointer is val, it stops moving and starts moving the fast pointer from back to front. When the value pointed by the fast pointer is not val, the value pointed by fast is assigned to slow. , and then slow continues to traverse backwards
public int removeElement(int[] nums, int val) {
int right = nums.length - 1;
int left = 0;
for (left = 0; left <= right; ) {
if ((nums[left] == val) & amp; & amp; (nums[right] != val)) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
if (nums[left] != val) left + + ;
if (nums[right] == val) right--;
}
return left ;
}
Special topic on odd-even movement of elements
Sort an array by parity. Given an array A of nonnegative integers, return an array in which all even elements of A are followed by all odd elements. You can return any array that satisfies this condition as an answer.
For example:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3] and [4,2,1,3] are also accepted.
The most direct way is to use a temporary array, search and copy all even numbers to the front part of the new array in the first pass, and find and copy all odd numbers to the back part of the array in the second pass. This method is relatively simple to implement, but it will face the interviewer’s soul question: “Is there a method with space complexity of O(1)”. We can use the collision type double pointer method
Maintain two pointers left=0 and right=arr.length-1. Left starts from 0 and checks each position one by one to see if it is an even number. If so, skip it. If it is an odd number, stop. Then right checks from right to left, if it is an odd number, it skips the even number and stops. Then swap array[left] and array[right]. Then continue the patrol loop until left>=right.
public static int[] sortArrayByParity(int[] A) {
int left = 0, right = A.length - 1;
while (left < right) {
if (A[left] % 2 > A[right] % 2) {
int tmp = A[left];
A[left] = A[right];
A[right] = tmp;
}
if (A[left] % 2 == 0) left + + ;
if (A[right] % 2 == 1) right--;
}
return A;
}
Array rotation problem
Given an array, rotate the elements in the array k positions to the right, where k is a non-negative number.
For example:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
explain:
Rotate 1 step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]
The method is as follows: 1. First flip the entire array, for example [1,2,3,4,5,6,7]. We first flip it as a whole into [7,6,5,4,3,2,1]. 2 is divided into left and right parts from k. Here, it is divided into two groups [7,6,5] and [4,3,2,1] based on k. 3 Finally, flip the two again to get [5,6,7] and [1,2,3,4], and the final result is [5,6,7,1,2,3,4]
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start + = 1;
end -= 1;
}
}
Interval topic of arrays
Given a sorted array of integers nums without duplicate elements. Returns a list of the smallest ordered ranges that exactly cover all the numbers in the array. That is, every element of nums is covered by exactly some interval range, and there is no number x that belongs to a range but not nums . Each interval range [a,b] in the list should be output in the following format: “a->b” if a != b”a” if a == b
Example 1:
Input: nums = [0,1,2,4,5,7]
Output: [“0->2″,”4->5″,”7”]
Explanation: The interval range is:
[0,2] –> “0->2”
[4,5] –> “4->5”
[7,7] –> “7”
Example 2:
Input: nums = [0,2,3,4,6,8,9]
Output: [“0″,”2->4″,”6″,”8->9”]
Explanation: The interval range is:
[0,0] –> “0”
[2,4] –> “2->4”
[6,6] –> “6”
[8,9] –> “8->9”
public static List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<>();
// slow initially points to the starting position of the first interval
int slow = 0;
for (int fast = 0; fast < nums.length; fast + + ) {
// fast traverses backward until continuous increment is no longer satisfied (i.e. nums[fast] + 1 != nums[fast + 1])
// Or fast reaches the array boundary, then the current continuous increasing interval [slow, fast] is traversed and written into the result list.
if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {
//Write the current interval [slow, fast] into the result list
StringBuilder sb = new StringBuilder();
sb.append(nums[slow]);
if (slow != fast) {
sb.append("->").append(nums[fast]);
}
res.add(sb.toString());
// Update the slow pointer to fast + 1 as the starting position of the next interval
slow = fast + 1;
}
}
return res;
}
String replacement space problem
Please implement a function to replace each space in a string with ” “. For example, when the string is We Are Happy, the replaced string is We Are Happy. First, you must consider what to use to store the string. If it is a char array with an immutable length, you must apply for a larger space. If you use a variable-length space to manage the original array, or if the original array is large enough, you may not be able to apply for O(n)-sized space. Let’s look at it one by one. First, if the length is not variable, we must apply for a larger space, and then directly replace the spaces where spaces appear in the original array with . The code is as follows:
public String replaceSpace(StringBuffer str) {
String res="";
for(int i=0;i<str.length();i + + ){
char c=str.charAt(i);
if(c==' ')
res + = " ";
else
res + = c;
}
return res;
}
For the second case, the first thing we think of is to traverse the entire string from beginning to end. When encountering a space, move the following elements back 2 positions. However, as mentioned before, such a problem will cause the following elements to For a large number of moves, the time complexity is O(n^2), and it is very easy to time out during execution. A better way is to traverse the string first, so that the total number of spaces in the string can be counted, and the length of the string after replacement can be calculated. For each space replaced, the length increases by 2, which is the length of the string after replacement. It is: the length of the new string = original length + 2*number of spaces. Next, copy and replace from the end of the string. Use two pointers, fast and slow, to point to the end of the original string and the new string respectively. Then: slow does not Move, move fast forward: ●If the point pointed to is not a space, copy it to the slow position, and then fast and slow move forward at the same time; ●If fast points to a space, insert one at the slow position, and fast will only move step. Perform the above two steps in a loop to complete the replacement. The detailed process is as follows:
public String replaceSpace(StringBuffer str) {
if (str == null)
return null;
int numOfblank = 0;//Number of spaces
int len = str.length();
for (int i = 0; i < len; i + + ) { //Calculate the number of spaces
if (str.charAt(i) == ' ')
numOfblank + + ;
}
str.setLength(len + 2 * numOfblank); //Set the length
int fast = len - 1; //Two pointers
int slow = (len + 2 * numOfblank) - 1;
while (fast >= 0 & amp; & amp; slow > fast) {
char c = str.charAt(fast);
if (c == ' ') {
fast--;
str.setCharAt(slow--, '0');
str.setCharAt(slow--, '2');
str.setCharAt(slow--, '%');
} else {
str.setCharAt(slow, c);
fast--;
slow--;
}
}
return str.toString();
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57128 people are learning the system