Leetcode
2020.04.16 13:56
287. Find the Duplicate Number
조회 수 211 추천 수 0 댓글 0
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2] Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
class Solution { public int findDuplicate(int[] nums) { HashMap<Integer, Integer> hmap = new HashMap<>(); for(int num : nums){ hmap.put(num, hmap.getOrDefault(num,0)+1); } for(Map.Entry<Integer, Integer> item : hmap.entrySet()){ if(item.getValue() > 1){ return item.getKey(); } } return -1; } }
class Solution { public int findDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for(int num : nums){ if(set.contains(num)){ return num; } set.add(num); } return -1; } }
class Solution { public int findDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1; i<nums.length; i++){ if(nums[i] == nums[i-1]){ return nums[i]; } } return -1; } }
[문제] https://leetcode.com/problems/find-the-duplicate-number/