package com.striner.java.jzOffer;

import java.util.*;

public class FindRepeatNumber03 {

//剑指 Offer 03. 数组中重复的数字

//找出数组中重复的数字。

//

//

//在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

//

//示例 1：

//

//输入：

//[2, 3, 1, 0, 2, 5, 3]

//输出：2 或 3

//

//

//限制：

//

//2 <= n <= 100000

//https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

public static void main(String[] args) {

}

// 方法1：bitmap

public int findRepeatNumber(int[] nums) {

int len = nums.length;

BitSet bitSet = new BitSet(len);

for(int i = 0; i < len; i++) {

if(bitSet.get(nums[i])) return nums[i];

bitSet.set(nums[i]);

}

return -1;

//执行结果： 通过

//执行用时： 3 ms , 在所有 Java 提交中击败了 56.94% 的用户

//内存消耗： 45.8 MB , 在所有 Java 提交中击败了 92.97% 的用户

}

// 方法2：map

public int findRepeatNumber2(int[] nums) {

int len = nums.length;

Map<Integer, Integer> map = new HashMap<>();

for(int i = 0; i < len; i++) {

if(map.get(nums[i]) != null) return nums[i];

map.put(nums[i], nums[i]);

}

return -1;

//执行结果： 通过

//执行用时： 8 ms , 在所有 Java 提交中击败了 18.56% 的用户

//内存消耗： 46.5 MB , 在所有 Java 提交中击败了 49.47% 的用户

}

// 方法3：set

public int findRepeatNumber3(int[] nums) {

int len = nums.length;

Set<Integer> set = new HashSet<>();

for(int i = 0; i < len; i++) {

if(!set.add(nums[i])) return nums[i];

set.add(nums[i]);

}

return -1;

//执行结果： 通过

//执行用时： 7 ms , 在所有 Java 提交中击败了 37.69% 的用户

//内存消耗： 46.6 MB , 在所有 Java 提交中击败了 48.37% 的用户

}

}