Use a customized similar set to speed up the efficiency


  • 0

    We don't need to put all candies into the set since the result will not greater than the half mount of candies.

    public class Solution {
        public int distributeCandies(int[] candies) {
            BooleanSet set = new BooleanSet();
            int halfSize = candies.length / 2;
            int count = 0;
            for (int candy : candies) {
                if (!set.contains(candy)) {
                    set.add(candy);
                    if (++count >= halfSize) {
                        return halfSize;
                    }
                }
            }
            return count;
        }
    }
    
    class BooleanSet {
        private static int MAX = 100000;
        private boolean[] buffer;
        
        public BooleanSet() {
            buffer = new boolean[MAX * 2 + 1];
        }
        
        private int index(int candy) {
            return MAX + candy;
        }
        
        public boolean contains(int candy) {
            return buffer[index(candy)];
        }
        
        public void add(int candy) {
            buffer[index(candy)] = true;
        }
    }
    

Log in to reply
 

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