Unrolled linked list: 162ms in C++


  • 1
    H

    We maintain a list<vector<int>> which keeps the size of each vector <2 * N. Once a new element is added into a vector and its size exceeds 2 * N, we move half elements in it into a new vector, and insert the new one into the the list.

    The performance depends on N. The best value is sqrt(size) when its complexity reaches O(sqrt(size)) for both add & query.

    For detailed analysis, see Wiki page of Unrolled linked list

    An example for N=3

    // Before
    [ [1, 2, 3] ] -> [ [4, 5, 6, 7, 8, 9] ] -> [ [11, 12, 13] ]
    // Add 10
    [ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
    // Find the median (6th element)
    [ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
      ^ this block contains [0, 3)-th elements, skip
    [ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
                        ^ this block contains [3, 6)-th elements, skip
    [ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
                                         ^ this block contains [6, 10)-th elements, so the 6th element could be v[6 - 6] == v[0] in this block
    

    Code:

    class MedianFinder {
        list<vector<int>> l;
        int size = 0;
        static const int N = 128;
        void insert_v(vector<int> &v, int x)
        {
            v.resize(v.size() + 1); int i;
            for (i = v.size() - 1; i>=1; --i)
                if (v[i-1] > x)
                    v[i] = v[i-1];
                else
                {
                    v[i] = x;
                    break;
                }
            if (!i) v[0] = x;
        }
    public:
        /** initialize your data structure here. */
        MedianFinder() {
            l.clear();
            size = 0;
        }
        
        void addNum(int num) {
            if (l.empty())
                l.push_back(vector<int> {num});
            else
                for (auto it = l.begin() ; it != l.end(); ++it)
                    if (next(it) == l.end() || num < *next(it)->begin())
                    {
                        insert_v(*it, num);
                        if (it->size() > 2 * N)
                        {
                            vector<int> new_v(it->begin() + N, it->end());
                            it->resize(N);
                            l.insert(next(it), std::move(new_v));
                        }
                        break;
                    }
            ++size;
          //  cout << "Added " << num << endl;
        }
        
        double findMedian() {
            int cnt = 0;
            int sum = 0; /*
            for (auto &&block: l)
            {
                cout << "Block: "; for(int i: block) cout << i << ",";
                cout << " \t";
            }
            cout << endl; */
            for (auto it = l.begin(); it != l.end(); ++it)
            {
                int r = cnt + it->size();
                if (size / 2 >= cnt && size / 2 < r)
                    sum += (*it)[size / 2 - cnt];
                if (size % 2 == 0)
                    if (size / 2 - 1 >= cnt && size / 2 - 1 < r)
                        sum += (*it)[size / 2 - 1 - cnt];
                cnt = r;
            }
            //cout << "Found!" << endl;
            return size % 2 ? sum : sum / 2.0;
        }
    };
    

Log in to reply
 

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