Java in developing the fastest solution


  • 1
    G

    ~115ms
    To get things done, use hashset to eliminate duplicates.

    	public static int distributeCandies ( int[] candies ) {
    		HashSet<Integer> set = new HashSet<>();
    		for ( int i = 0; i < candies.length; set.add(candies[i++]) );
    		return Math.min(set.size(), candies.length/2);
    	}
    

    ~75ms
    For better runtime, we can allow early out by checking the largest possible value:

    	public static int distributeCandiesEarly ( int[] candies ) {
    		HashSet<Integer> set = new HashSet<>();
    		int max = candies.length/2;
    		for ( int c : candies ) {
    			set.add(c);
    			if ( set.size() == max ) return max;
    		}
    		return set.size();
    	}
    

    ~32ms
    For fastest runtime, we can use more memory with respect to the remarks:

    	public static int distributeCandiesCustomized ( int[] candies ) {
    		int half = candies.length / 2;
    		boolean[] bucket = new boolean[200001];
    		int count = 0;
    		for ( int i = 0; i < candies.length; ++i ) {
    			if ( !bucket[candies[i]+100000] ) {
    				if ( count++ == half ) return half;
    				bucket[candies[i]+100000] = true;
    			}
    		}
    		return count;
    	}
    

  • 1

    @gzwongkk said in Java in developing the fastest solution:

    200001

    Nice explanation. Could you shed some light on how you come out with the number 200001?


Log in to reply
 

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