C++ with iterators


  • 14

    Just a mergesort solution, but using iterators (instead of indexes) and inplace_merge.

    class Solution {
    public:
        int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) {
            if (end - begin <= 1)
                return 0;
            auto mid = begin + (end - begin) / 2;
            int count = sort_and_count(begin, mid) + sort_and_count(mid, end);
            for (auto i = begin, j = mid; i != mid; ++i) {
                while (j != end and *i > 2L * *j)
                    ++j;
                count += j - mid;
            }
            inplace_merge(begin, mid, end);
            return count;
        }
    
        int reversePairs(vector<int>& nums) {
            return sort_and_count(nums.begin(), nums.end());
        }
    };
    

  • 0
    V

    Love the brevity and inplace_merge. BTW, I think you meant to remove "1" from "Solution1".


  • 0

    @votrubac Oh, right. Thanks. Just a remainder of testing more variations (that turned out less nice). Btw, the "mid" iterator caused me to look up the proper name. The inplace_merge documentation) calls it "middle". But then I wondered why it uses "first" and "last" instead of "begin" and "end". Made a StackOverflow question of this.


  • 0
    S

    Thanks Stefan. It's quite cool to combine with merge sort. :-)
    Just came up an idea, for the count accumulation part, I would made the following optimisation:

    ...
        int mid = (start+end)/2;
    ...
        for (int j = mid+1; j <= end; ++j) {
            long long pivot = 2 * nums[j];
            std::vector<int>::iterator itBegin = nums.begin()+start;
            std::vector<int>::iterator itEnd = nums.begin()+mid+1;
            std::pair<std::vector<int>::iterator, std::vector<int>::iterator> range = std::equal_range(itBegin, itEnd, 2*nums[j]);   <<< the equal_range here would be more efficient since each of the two partitions are already in order
            if (range.second != itEnd) {
                count += std::distance(range.second, itEnd);
            }
        }
    ...
    

  • 0

    @silentspring Your code is hard to read, could you please format it?


  • 0
    Y

    Hi, @StefanPochmann

    Thank you so much for your concise, clean and elegant code!
    This is my favorite implementation of "count inversions" problem so far.

    One trivial question.
    Will the expression " *i > 2L * *j " implicitly convert (*i) to "long" as well?
    Will it work if " 1L *i > 2 * *j " ?
    Is there anyway to avoid conversion? I was thinking x/2+x%2 > y, where x = *i, and y = *j. But it does not work for negative numbers.
    Maybe you have some smarter ways :D
    Thanks.


  • 0
    S

    @StefanPochmann
    Sorry I did not know how to quote my code in this pane.
    Updated my code snippet. And also apologise for misspelling your name. :-)


  • 0

    @silentspring That's not an optimisation. You made it slower. It's only O(m log m) while mine is O(m), where m is the size of the halves. Plus you have the overhead of calling functions.

    Btw, what is long long pivot = 2 * nums[j]; supposed to achieve? Protect against overflow? When you store it as long long, the overflow has already happened. Well it doesn't matter because, um... you're not using pivot anyway. And why use equal_range when you then only use its upper_bound part?


  • 0

    @yren2 said in C++ with iterators:

    Will the expression " *i > 2L * *j " implicitly convert (*i) to "long" as well?

    I don't know. But I suspect it does. Doesn't matter, though.

    Will it work if " 1L *i > 2 * *j " ?

    No, doesn't even compile. If you add * in the left side it compiles, but it's pointless. My 2L * *j goes to long before the multiplication, protecting against overflow. Your 2 * *j doesn't.

    Is there anyway to avoid conversion? I was thinking x/2+x%2 > y, where x = *i, and y = *j. But it does not work for negative numbers.

    You were close! (*i >> 1) + (*i & 1) > *j works.

    Seems to be slower than mine, though. I did a test magnifying the time impact:

        int add;
        for (int k=0; k<100; k++) {
            add = 0;
            for (auto i = begin, j = mid; i != mid; ++i) {
                while (j != end and *i > 2L * *j)
                    ++j;
                add += j - mid;
            }
        }
        count += add;
    

    Tested with three different expressions five times each, here are the acceptance times in ms:

    *i > 2L * *j => 933 949 942 1178 936
    *i > long(*j) << 1 => 1082 993 992 979 1059
    (*i >> 1) + (*i & 1) > *j => 1312 1332 1135 1129 1149


  • 0
    J

    Hi, stefan, I love your coding style so much.
    I can always learn a lot from your posts!


  • 0
    S

    @StefanPochmann
    The pivot is a rubbish code which should have been deleted.

    Oh ... I got your idea. Your is O(n) which is the most optimised.
    For my version: I also should have used the std::upper_bound to get the first element within the 1st half which is greater than 2*nums[j]. But yeah, it makes it slower than yours.
    Thank you very much!


  • 0

    Great concise solution.

    For the counting part, it seems that we could have an early termination right after while loop if j has reached end before i reaches mid:

    • if (j == end) { count += (mid-i)*(end-mid); break; }.

    This helps for arrays whose first half values are much bigger than second half, e.g., [1000@10, 1000@1].


  • 0
    C

    @yren2 *j * 2L automatically converts *j from int to long, same for *i > *j * 2L


Log in to reply
 

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