[C++] Clean Code - 2 Solutions: Set and Sort


  • 8

    Set - O(N) time, O(N) space
    We can use a set to count all unique kinds of candies, but even all candies are unique, the sister cannot get more than half.
    (Even though in reality my GF would always get more than half.)

    class Solution {
    public:
        int distributeCandies(vector<int>& candies) {
            unordered_set<int> kinds;
            for (int kind : candies) {
                kinds.insert(kind);
            }
            return min(kinds.size(), candies.size() / 2);
        }
    };
    

    Using range constructor as @i_square suggested:

    class Solution {
    public:
        int distributeCandies(vector<int>& candies) {
            return min(unordered_set<int>(candies.begin(), candies.end()).size(), candies.size() / 2);
        }
    };
    

    Sort - O(N logN) time, O(1) space
    Or we can sort the candies by kinds, count kind if different than the prevous:

    class Solution {
    public:
        int distributeCandies(vector<int>& candies) {
            size_t kinds = 0;
            sort(candies.begin(), candies.end());
            for (int i = 0; i < candies.size(); i++) {
                kinds += i == 0 || candies[i] != candies[i - 1];
            }
            return min(kinds, candies.size() / 2);
        }
    };
    

    The counter can start from 1 since there is no test case for empty input:

    class Solution {
    public:
        int distributeCandies(vector<int>& candies) {
            size_t kinds = 1;
            sort(candies.begin(), candies.end());
            for (int i = 0; i < candies.size(); i++) {
                kinds += candies[i] != candies[i - 1];
            }
            return min(kinds, candies.size() / 2);
        }
    };
    

  • 0
    V

    @alexander The complexity of this solution is O(n * log n), as set keeps it's content sorted so every insert requires O(log n). You can get O(n) if you use unordered_set instead.


  • 0

    I normally use set to make code looks cleaner.
    Changed. Thanks.


  • 2

    Thanks for your share.
    The 1st solution is same to mine, but I use range constructor instead of default constructor.
    unordered_set<int> candy_kinds(candies.begin(), candies.end());
    In the 2nd solution, it is no need to deal with i == 0, just initialize kinds = 1.

    class Solution {
    public:
        int distributeCandies(vector<int>& candies)
        {
            size_t kinds = 1;
            sort(candies.begin(), candies.end());
            for (int i = 1; i < candies.size(); ++i)
                if (candies[i] != candies[i - 1])
                    ++kinds;
            return min(kinds, candies.size() / 2);
        }
    };
    

  • 0

    @i_square Good point to use the range constructor for the set solution, could make the code a lot shorter.
    For the sort solution. I was first doing the same thing as you. Then I was paranoid about a empty input, so I changed it to that way. Even there is no such a test case. :)


  • 1

    @alexander The Note 1 : The length of the given array is in range [2, 10,000], and will be even points out that there's no need to worry about the input. May it help you. :smile:


  • 0

    @i_square haha, really should have spend the time to read all the description LOL.


  • 2
    Z

    Good code! You can also use bitset, which is much faster

    int distributeCandies(vector<int>& candies) {
            bitset<200001> hash;
            int count = 0;
            for (int i : candies) {
                if (!hash.test(i+100000)) {
                   count++;
                   hash.set(i+100000);
                }
            }
            int n = candies.size();
            return min(count, n/2);
        }
    

  • 0
    L
    This post is deleted!

Log in to reply
 

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