QuickSort inspired solution - O(n) performance and O(1) space


  • 0
    C

    Hi, I just want to share my QuickSort inspired solution that still achieves O(n) performance and O(1) space.

    public class Solution
    {
        public int singleNumber(int[] nums)
        {
            int bit = 0;
            int init = 0;
            int last = nums.length - 1;
    
            while (true)
            {
                int head = init;
                int tail = last;
    
                while (head <= tail)
                {
                    while (head < nums.length)
                    {
                        if (is_even(nums[head], bit)) break;
                        else head += 1;
                    }
    
                    while (0 < tail)
                    {
                        if (is_odd(nums[tail], bit)) break;
                        else tail -= 1;
                    }
    
                    if (head < tail)
                    {
                        swap(nums, head++, tail--);
                    }
                }
    
                if ((head - init) == 1)
                {
                    return nums[init];
                }
                if ((last - tail) == 1)
                {
                    return nums[last];
                }
    
                if ((head - init) % 3 == 1)
                {
                    last = head - 1;
                }
                else
                {
                    init = tail + 1;
                }
    
                bit++;
            }
        }
    
        private static boolean is_odd(int num, int bit)
        {
            return ((num >> bit) & 1) == 1;
        }
    
        private static boolean is_even(int num, int bit)
        {
            return !is_odd(num, bit);
        }
    
        private static void swap(int[] nums, int i, int j)
        {
            if (i == j) return;
    
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

Log in to reply
 

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