My Java one-pass solution: Dijkstra's three-way partioning (Netherland flag problem)


  • 0
    G

    Dijskstra's three-way partitioning is useful in quick sort dealing with duplicates in array. Conceptually this method keeps two pointers that group elements equal to pivot. (if lt <= i <= gt, then A[i] == pivot)

        public class Solution {
        //  version: Dijskstra's three-way partitioning
        public void sortColors(int[] A) {
            int n = A.length;
            if (n < 2) return;
            int lt = 0;
            int gt = n - 1;
            int i = 0;
            while (i <= gt) {
                //  #1 is the pivot
                if (A[i] < 1) exch(A, i++, lt++);
                else if (A[i] > 1) exch(A, i, gt--);
                else i++;
            }
        }
        
        private void exch(int[] A, int p, int q) {
            int temp = A[p];
            A[p] = A[q];
            A[q] = temp;
        }
    }

Log in to reply
 

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