package linkedandlist;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* @authoryuanxindong
* @date: 2020/6/14 8:40 下午
*
*/
public class FinadListRePeatNum {
public static void main(String[] args) {
int[] nums = new int[]{
2, 3, 1, 0, 2, 53
};
int repeatNumberV1 = findRepeatNumberV1(nums);
System.out.println("重复数字1:" + repeatNumberV1);
int repeatNumberV2 = findRepeatNumberV2(nums);
System.out.println("重复数字2:" + repeatNumberV2);
int repeatNumberV3 = findRepeatNumberV3(nums);
System.out.println("重复数字3:" + repeatNumberV3);
}
/**
* 暴力遍历对比
* 时间复杂度为 O(n^2)
*/
private static int findRepeatNumberV1(int[] nums) {
if (nums == null) {
return -1;
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return -1;
}
/**
* 空间换时间使用set的特性来判断是否有重复
*
* @param nums
* @return 时间复杂度为O(n)
*/
private static int findRepeatNumberV2(int[] nums) {
if (nums == null) {
return -1;
}
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (!set.add(nums[i])) {
return nums[i];
}
}
return -1;
}
/**
* 先通过将数组排序,再进行便利比较前后元素。等于就说明重复
* 排一次顺序是logn,for循环便利一次是N
* 时间复杂度:O(NlogN)
*/
private static int findRepeatNumberV3(int[] nums) {
if (nums == null) {
return -1;
}
Arrays.sort(nums);
for (int i = 0 ; i< nums.length; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
return -1;
}
}