This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Problem description

Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the last half of the array.

Example:

Input: [1, 2, 3, 4]

Output:,3,2,4 [1]

To analyze problems

This problem we can use the double pointer method to solve, the specific idea is as follows.

  1. First, we apply two Pointers I and j to the left and right ends of nums, that is, I =0 and j=n-1.
  2. When I points to an odd position, execute I = I +1 until an even number is encountered.
  3. When j points to an even position, perform j=j+1 until an odd number is encountered.
  4. The values of nums[I] and nums[j] are then swapped
  5. Repeat until I ==j.

Let’s look at the implementation of the code.

Class Solution(object): def exchange(self, nums): def exchange(self, nums) =len(nums)-1 While I < j and nums[I] % 2 == 1: While I < j and nums[j] % 2 == 0: j = j - 1 nums[i], nums[j] = nums[j], nums[i] return numsCopy the code

In fact, we can also use the fast and slow pointer method to solve this problem. First, we define two Pointers fast and slow. The function of fast is to search forward where the odd number is, while the function of slow is to point to where the next odd number should be stored. As FAST moves forward, when it searches for an odd number, it swaps it with NUMs [slow], and then moves Slow forward one position, repeating the process until FAST points to the end of the array.

Class Solution: def exchange(self, nums): slow = 0 fast = 0 # change nums[fast] if nums[fast] % 2 == 1 nums[slow], nums[fast] = nums[fast], nums[slow] slow=slow+1 fast=fast+1 return numsCopy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).