LintCode 1794 · Count Duplicates.java

	// Approach #1 - O(n) T O(n) S - Just count,
	// and be careful it's not about 1st appearance, it's about the 2nd appear...; it's testing the data structure: list, map.
	public class Solution {
	/**
	* @param nums: a integer array
	* @return: return an integer denoting the number of non-unique(duplicate) values
	*/
	public List<Integer> countduplicates(List<Integer> nums) {
	// write your code here
	List<Integer> duplicates = new LinkedList<>();
	if (nums == null || nums.size() < 2) {
	return duplicates;
	}
	Map<Integer, Boolean> sawNumbers2AddedYet = new HashMap<>();
	for (int num : nums) {
	if (sawNumbers2AddedYet.containsKey(num)) {
	if (!sawNumbers2AddedYet.get(num)) {
	duplicates.add(num);
	sawNumbers2AddedYet.put(num, true);
	}
	} else {
	sawNumbers2AddedYet.put(num, false);
	}
	}
	return duplicates;
	}
	}

view raw LintCode 1794 · Count Duplicates.java hosted with ❤ by GitHub