Solution with radix sorting in O(n), 8ms C++


  • 0
    P

    Hello,

    I wrote this solution using radix sort on the 4 bytes of integers (and counting sort).
    Runtime is pretty good, 8ms, and complexity is O(n) (with O(n) storage):

    class Solution {
        static void count_sort(const vector<int>& a, int byte, vector<int> &out) {
            const int shift = 8 * byte;
            
            size_t cts[256] = {};
            for (size_t i = a.size(); i-- > 0;) {
                cts[(static_cast<unsigned>(a[i]) >> shift) & 0xFF] += 1;
            }
            
            for (size_t i = 1; i < 256; ++i) {
                cts[i] += cts[i - 1];
            }
            
            for (size_t i = a.size(); i-- > 0;) {
                out[--cts[(static_cast<unsigned>(a[i]) >> shift) & 0xFF]] = a[i];
            }
        }
        static void split_reverse_neg(const vector<int> &a, vector<int> &out) {
            size_t cts[2] = {};
            for (size_t i = a.size(); i-- > 0;) {
                cts[a[i] < 0 ? 0 : 1] += 1;
            }
            const size_t negs = cts[0];
            cts[1] += cts[0];
            
            for (size_t i = a.size(); i-- > 0;) {
                out[--cts[a[i] < 0 ? 0 : 1]] = a[i];
            }
        }
    public:
        int longestConsecutive(vector<int>& nums) {
            vector<int> tmp(nums.size());
            
            count_sort(nums, 0, tmp);
            count_sort(tmp, 1, nums);
            count_sort(nums, 2, tmp);
            count_sort(tmp, 3, nums);
            split_reverse_neg(nums, tmp);
            nums.swap(tmp);
            
            size_t max_len = 1;
            for (size_t i = 1, n = nums.size(), len = 1; i < n; ++i) {
                if (nums[i] == nums[i - 1] + 1) {
                    ++len;
                    if (len > max_len) {
                        max_len = len;
                    }
                } else if (nums[i] != nums[i - 1]) {
                    len = 1;
                }
            }
            
            return max_len;
        }
    };

Log in to reply
 

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