C++ 12ms, defeat 94% submission, O(n) time complexity


  • -1
    W

    Use radix sort.

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            
            radix_sort(nums);
            
            int ans = 1, now = 1, last = nums[0];
            for (int i=1; i<nums.size(); i++) {
                if (nums[i] == nums[i-1]) continue;
                if (nums[i] == last+1) {
                    now++;
                    ans = max(ans, now);
                    last++;
                }else {
                    now = 1;
                    last = nums[i];
                }
            }
            return ans;
        }
        
        void radix_sort(vector<int>& nums) {
            int n = nums.size();
            t0 = new int[n+4];
            t1 = new int[n+4];
            pos = new int[n+4];
            neg = new int[n+4];
            
            int n1=0, n2=0, maxn=nums[0], minn=nums[0];
            for (int i=0; i<n; i++) {
                if (nums[i] >= 0) {
                    pos[n1++] = nums[i];
                }else {
                    neg[n2++] = nums[i];
                }
                maxn = max(maxn, nums[i]);
                minn = min(minn, nums[i]);
            }
            
            sort(pos, n1, last_bit(maxn, 1));
            sort(neg, n2, last_bit(minn, 0));
            
            for (int i=0; i<n2; i++) {
                nums[i] = neg[i];
            }
            for (int i=0; i<n1; i++) {
                nums[n2+i] = pos[i];
            }
            
            delete[] t0;
            delete[] t1;
            delete[] pos;
            delete[] neg;
        }
        
        int last_bit(int x, int bit) {
            int i;
            for (i=31; i>=0; i--) {
                int t = (((unsigned int)x) >> i) & 0x1;
                if (t == bit) return i;
            }
            return 0;
        }
        
        void sort(int A[], int n, int max_bit_pos) {
            for (int i=0; i<=max_bit_pos; i++) {
                int n0 = 0, n1 = 0;
                
                for (int j=0; j<n; j++) {
                    if (((unsigned int)A[j] >> i) & 0x1) {
                        t1[n1++] = A[j];
                    }else {
                        t0[n0++] = A[j];
                    }
                }
                
                for (int j=0; j<n0; j++) {
                    A[j] = t0[j];
                }
                for (int j=0; j<n1; j++) {
                    A[n0+j] = t1[j];
                }
            }
        }
        
        int *t0, *t1, *pos, *neg;
    };

  • 0

    After sorting this problem seems no longer a problem, I think this is not a trick instead it's against the requirement O(n).


Log in to reply
 

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