One, foreword

Hello everyone, this is the 16th article in a series of articles titled “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Leetcode’s key Offer topic
  • Code cloud warehouse address

Second, the subject

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 second half.

Example 1:

Input: nums = [1,2,3,4] output: [1,3,2,4] note: [3,1,2,4] is also one of the correct answers.Copy the code

Tip:

  1. 0 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

Third, the problem solving

Subject in the form of double pointer, create a new, such as the length of the empty array and two Pointers, a pointer to an array of the left, the other one to the right side of the array, if it is odd, on the left side of the joined arrays, and then the left pointer moves to the right one, if it is even, then the pointer right shift to the left one, add elements to the array.

3.1 code

static public int[] exchange(int[] nums) { int [] a=new int[nums.length]; int length = nums.length; int j=0,k=0; for (int i = 0; i < length; i++) { if(nums[i]%2! =0){ a[j++]=nums[i]; }else{ k++; a[length-k]=nums[i]; } } return a; }Copy the code

3.2 Execution Effect

3.3 complexity

  • Time complexity O (n)
  • Space complexity O (n)

Four, summary

The first two questions are too disgusting, jumped to this question, no hair brush question, or from the simple question to find some confidence.