OJ questions related to complexity (leetcode, C language, complexity, vanishing numbers, rotating array)

Two about complexity LeetCode OJ topic

1. Missing numbers
2. Rotation array

Code ：C Language

1. Missing numbers

Click to go to LeetCode see Missing numbers

1.1 Title Description

requirement ： The time complexity should be within O(n) Inside

1.2 Solution and code implementation

1.2.1 Ideas 1

1. malloc An additional number is n+1 Array of , And all initialized to -1.
2. Traverse the data to be entered , What is this number , Fill in the corresponding position of the array .
3. Traverse the array again , Which position is -1, Then the subscript of which position is the missing number .
   
   ps：Drawio Your drawing is very good ！！！ If necessary, you can guide Microsoft Store Search apps Drawio, Download the genuine version directly .

---

• Time complexity ：O(n), Meet the requirements of the topic
• Spatial complexity ：O(n)
• The code part is also relatively simple , It's not going to happen here .

1.2.2 Ideas 2

• Use XOR , Here, I'll first give you some knowledge about XOR .
• What is XOR ？
  In logic , Logical arithmetic is different from or （exclusive or） Is a logical disjunctive type of two operands , The symbol is XOR or EOR or ⊕（ Commonly used in programming languages ^）.
  But different from the general logic or , The value of the exclusive or operator is true only if one of the two operands is true , And the value of the other is not true . Into a proposition , Namely ：“ The two values are different .” or “ There is and only one is true .”
• The characteristic of XOR ：

1. The result of two identical numbers exclusive or is 0.
2. XOR is out of order . Bitwise XOR , Same as 0, Dissimilarity is 1.
3. 0 And any number exclusive or result is the number itself

---

Let's get to the point , The solution is as follows ：

1. Create a variable x, And the initial value is 0
2. x It is XOR with the input data
3. x and 0~n The numbers between are exclusive or once , final x That is, the missing number

C The language code is implemented as follows ：

int missingNumber(int* nums, int numsSize) {
    
	int x = 0;
	for (int i = 0; i < numsSize; ++i)
	{
    
		x ^= nums[i];
	}
	for (int j = 0; j < numsSize+1; ++j)
	{
    
		x ^= j;
	}
	return x;
}

1. Time complexity ：O(n)
2. Spatial complexity ：O(1)

---

2. Rotation array

Click to go to LeetCode see Rotation array

2.1 Title Description

Rotation array （ Rotated array ） Requirements are as follows ：

1. Think of three different solutions
2. Time complexity O(n)
3. Spatial complexity O(1)

2.2 Solution and code implementation

2.2.1 Ideas 1

1. Rotate one at a time
2. rotate K Time

---

• Time complexity ：O(N^2)
• Spatial complexity ：O(1)
• Unqualified （ can't make a good living OJ）

2.2.2 Ideas 2

Space for time

1. Open up an extra array
2. Put the back of the original array k Copy data to the front of the new array k A place
3. Put the front of the original array n-k Copy data to the back of the new array n-k A place
4. Then copy the new array back to the original array , End of rotation
   

---

• Time complexity ：O(n)
• Spatial complexity ：O(n)
• Unqualified （ But I can pass OJ）

2.2.3 Ideas 3

• Put it back in place

1. front n-k An inverse
2. after k An inverse
3. Global inversion
   

---

• Time complexity ：O(n)
• Spatial complexity ：O(1)
• In line with the question , It is the best solution and the hardest to think of

C The language code is implemented as follows ：

int* reverse(int* nums, int left, int right)
{
    
	while (left < right)
	{
    
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		left++;
		right--;;
	}
	return nums;
}

void rotate(int* nums, int numsSize, int k) {
    
	k %= numsSize;
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, 0, numsSize - 1);
}

---

Learning record ：

• This article is arranged in 2022.6.21
• If there are mistakes, please give me more advice