LeetCode - array (elementary)

1. Given an array num, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.

Please note that you must operate on the array in place without copying it.

Input: num = [0,1,0,3,12]

Output: [1,3,12,0,0]

Solution idea: move the non-zero forward by exchanging the position of the first 0 and the first non-0 element.

[0,1,0,3,12] -- > 0 appears, and 1 is not 0, so replace 1 with 0, thus [1,0,0,3,12]. Then, find 3 with the first 0 exchange, and then find the 0 exchange after 12 with 3, so as to get [1,3,12,0,0]

void moveZeroes(int* nums, int numsSize)
{
	int count = 0;
	for (int i = 0; i < numsSize - 1; i++)
	{
		if (nums[i] == 0 && nums[i + 1] == 0)
		{
			count++;
		}else if (nums[i] == 0 && nums[i+1] != 0) {
				int temp = nums[i - count];
				nums[i - count] = nums[i + 1];
				nums[i + 1] = temp;
		}
	}

}

Operation results:

2. Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the array after removal. Don't use extra array space. You must only use O(1) extra space and modify the order of input array elements in place to change. You don't need to consider the elements in the array beyond the new length

Input: num = [3,2,2,3], Val = 3
Output: 2, Num = [2,2]
Explanation: the function should return a new length of 2, and the first two elements in num are both 2. You don't need to consider the elements in the array beyond the new length. For example, if the new length returned by the function is 2, and num = [2,2,3,3] or num = [2,2,0,0], it will also be regarded as the correct answer.

Idea: just like the idea of solving question 1, set val value to 0;

int removeElement(int* nums, int numsSize, int val){
    
	int count = 0;
    int c = 0;
for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] == val)
		{
			nums[i] = 0;
			count++;
		}
	}
	for (int i = 0; i < numsSize - 1; i++)
	{
		if (nums[i] == 0 && nums[i + 1] == 0)
		{
			c++;
		}
		else if (nums[i] == 0 && nums[i + 1] != 0) {
			int temp = nums[i - c];
			nums[i - c] = nums[i + 1];
			nums[i + 1] = temp;
		}
	}

	return numsSize - count;
}

Operation results:

Idea 2: set a counter from 0 to numsize. If the value of num[i] is val, the current one is exchanged with the last one, and then the last element is deleted; Otherwise, i++; Finally, numsize is returned.

int removeElement(int* nums, int numsSize, int val){
    
int i = 0;
while (i < numsSize)
{
	/*When we encounter nums[i]==val, we can exchange the current element with the last element and release the last element. This actually reduces the size of the array by 1*/
	if (nums[i] == val)
	{
		nums[i] = nums[numsSize - 1];
		numsSize--;//Array size -1
	}
	else
	{
		i++;
	}
}
return numsSize;
}

Operation results:

Summary: the second algorithm only needs to traverse once to get the result, while the first one needs to traverse once to set it to 0, and sort the second time, so the second method is more efficient in time; Both of them use the same space, so the second algorithm is more concise and efficient.

3. Give you an array num in ascending order. Please delete the repeated elements in place so that each element appears only once, and return the new length of the array after deletion. The relative order of elements should be 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 num. More formally, if there are k elements after deleting duplicates, the first k elements of num should save the final result.

Insert the final result into the first k positions of num and return K. Do not use extra space. You must modify the input array in place and complete it with O(1) extra space.

Input: num = [1,1,2]
Output: 2, Num = [1,2, _]
Explanation: the function should return a new length of 2, and the first two elements of the original array num are modified to 1, 2. There is no need to consider the elements in the array that exceed the new length.

Idea: by judging the same elements, go to the back row. Set the same elements to 10001 (the highest number prompted in the question is 10000) through the first traversal, and then sort them. From there, the repeated numbers are dragged to the back row a little, because there are many cycles, so the time consumed is relatively more.

int removeDuplicates(int* nums, int numsSize)
{
	int len = numsSize;
	int k = 0;
	int j = 0;
	for (k = 0; k < numsSize; k++)
	{
		for (j = k + 1; j < numsSize; j++)
		{
			if (nums[k] == nums[j])
			{
				nums[k] = 10001;
				len--;
			}
		}
	}
	int count = 0;
	for (int i = 0; i < numsSize - 1; i++)
	{
		if (nums[i] == 10001 && nums[i + 1] == 10001)
		{
			count++;
		}
		else if (nums[i] == 10001 && nums[i + 1] != 10001) {
			int temp = nums[i - count];
			nums[i - count] = nums[i + 1];
			nums[i + 1] = temp;
		}
	}
	
	return len;
}

Operation results:

Idea 2: point to the first through another variable, and then judge whether the next one is equal to it. If it is equal, skip it, and if it is not equal, put it after j;

int removeDuplicates(int* nums, int numsSize) {
	int i, j = 0;
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] != nums[j])
		{
			j++;
			nums[j] = nums[i];
		}
	}
	if (numsSize > 0) return j + 1;
	return j;
}

Summary: the first one is based on the idea of zero sorting, which sets the repetition outside the threshold, so that the results can be obtained after one sorting. The second is to delete the duplicate through one-time traversal. So the efficiency of the second kind will be higher.

4. Give you an ordered array num, please delete the repeated elements in place, so that the elements that appear more than twice only appear twice, and return the new length of the deleted array. Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.

Input: num = [1,1,1,2,2,3]
Output: 5, Num = [1,1,2,2,3]
Explanation: the function should return a new length of length = 5, and the first five elements of the original array are modified to 1, 1, 2, 2, 3. There is no need to consider the elements in the array that exceed the new length.

Idea: take len as a fixed element, give the element at i position to the element at len position, and move one backward. The judgment condition is that if there are two identical elements, and the third one is different, assign a value, otherwise len will remain unchanged.

int removeDuplicates(int* nums, int numsSize){
int len = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (len < 2 || nums[len - 2] != nums[i])
		{
			nums[len++] = nums[i];
		}
	}
	return len;
}

Operation results:

The above are the initial definition and solution of LeetCode array algorithm. My personal ability is limited, and the solution is still very astringent, for reference only.