This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

283, Move Zeroes- Move 0 to the end of the sequence

The question:

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

 Input: nums = [0,1,0,3,12]
 Output: [1,3,12,0,0]
Copy the code

Example 2:

 Input: nums = [0]
 Output: [0]
Copy the code

Constraints:

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you minimize the total number of operations done?

Analysis:

The requirement is to move all zeros to the end of the sequence. The case analysis shows that the relative order of non-zero digits must remain the same during the movement. To be more direct, use the bubble idea to move all zeros to the end of the sequence; Moreover, you can use double pointer, a logo is not zero current digital subscript currentIndex, another said the index to the position of the current traversal, thought is through iterates through all not the number of zero will move to occupy the front of 0 digital position, then we record the processing to the location of the data, the Numbers should be set to 0.

Problem solving:

Bubble thinking + double pointer thinking

1. The direct use of bubbling ideas
 /** * Bubble ideas to achieve **@param nums
   * @return* /
 public static int[] moveZerosVersion1(int[] nums) {
     final int length = nums.length;
     int temp;
     for (int i = 0; i < length - 1; i++) {
         if (nums[i] == 0) {
             int j = i;
             while (j < length - 1) {
                 temp = nums[j];
                 nums[j] = nums[j + 1];
                 nums[j + 1] = temp; j++; }}}return nums;
 }
Copy the code
2. Optimization of the use of direct bubbling ideas

In the process of moving 0 to the end of the sequence

 /** * Bubble idea to achieve optimization **@param nums
   * @return int[]
   */
 public static int[] moveZerosVersion2(int[] nums) {
     final int length = nums.length;
     // The number of times the digit 0 is moved
     int count = 0;
     int temp
     for (int i = 0; i < length - 1; i++) {
         if (nums[i] == 0) {
             int j = i;
             while (j < length - 1 - count) {
                 temp = nums[j];
                 nums[j] = nums[j + 1];
                 nums[j + 1] = temp; j++; } count++; }}return nums;
 }
Copy the code
3, the realization of double pointer idea
 /** * Double pointer implementation **@param nums
   * @return* /
 public static int[] moveZerosVersion3(int[] nums) {
     final int length = nums.length;
     int currentIndex = 0;
     int cursorIndex = 0;
 ​
     while (cursorIndex < length) {
         if (nums[cursorIndex] == 0) {
             cursorIndex++;
             continue;
         }
 ​
         nums[currentIndex] = nums[cursorIndex];
         currentIndex++;
         cursorIndex++;
     }
     // Set the tail element to 0
     for (int i = currentIndex; i < length; i++) {
         nums[i] = 0;
     }
 ​
     return nums;
 }
Copy the code