题目链接:https://leetcode-cn.com/problems/find-the-duplicate-number/
题目描述
分析
1. 嵌套for循环
2. 利用map查重
代码实现
public enum Q287 {
instance;
public int findDuplicate(int[] nums) {
if(nums.length<=1) return 0;
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
Integer count = map.get(num);
if(count==null){
map.put(num,1);
}else{
return num;
}
}
return 0;
}
public int findDuplicate1(int[] nums) {
int l=nums.length;
for(int i=0;i<l;i++){
for(int j=i+1;j<l;j++){
if(nums[i]==nums[j]){
return nums[i];
}
}
}
return 0;
}
// LeetCode 解法
public int findDuplicate2(int[] nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
public static void main(String[] args) {
// assert 1
System.out.println(Q287.instance.findDuplicate1(new int[]{1,1,3,4,5}));
// assert 3
System.out.println(Q287.instance.findDuplicate1(new int[]{1,2,3,4,3}));
// assert 0
System.out.println(Q287.instance.findDuplicate1(new int[]{1,2,3,4,5}));
// assert 4
System.out.println(Q287.instance.findDuplicate2(new int[]{1,2,3,4,4}));
}
}
