Java Single Pass


  • 5
    C

    Use two pointers. One for the place to insert 0 (zero) and another for the place to insert 2 (two).

    Iterate through this array, if 0 is found, swap its value with zero. if 2 is found, swap its value with two. If 1 is found, go to the next position until it exceeds two or fall behind by zero.

    public class Solution {
        public void sortColors(int[] nums) {
            if (nums == null || nums.length == 0) return;
            int zero = 0, count = 0, two = nums.length - 1;
            while (count <= two && count >= zero) {
                while (count <= two && count >= zero) {
                    if (nums[count] == 0) {
                        swap(nums, count, zero);
                        zero++;
                    }
                    if (nums[count] == 2) {
                        swap(nums, count, two);
                        two--;
                    }
                    if (nums[count] == 1) break;
                }
                count++;
            }
        }
        
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.