package arrays;

import java.util.HashSet;
import java.util.Set;

/**
 * 题目:
 * 给定一个不为空的整数数组,数组里面只有一个不重复的数字,要求找到这个数字
 * y: [5 5 6 7 7] 返回6
 *
 * @Author Gavin
 * @date 2021年12月08日 21:24
 */
public class array_3 {
 /**
 *解题思路1:使用set集合先把元素去重,然后把剩下的元素之和*2 减去数组里面元素的和就得到重复的那个元素了
 * 解题思路2: 使用异或运算,使数组里面的所有数进行与或运算,最后得到的值就是那个唯一的值
 * 异或运算就是两个相同的值异或的值为0,然后0和任何元素进行异或得到的是原来的值
 */

 //第一种:使用一个set集合
 //Time:O(n) Space: O(n)
 public static int solution(int[] arrays){
 Set<Integer> set=new HashSet<>();
 int sum=0,union=0;
 for(int pre:arrays){
 if(!set.contains(pre)){
 union+=pre;
 set.add(pre);
 }
 sum+=pre;
 }
 return 2*union-sum;
 }


 //第二种方式,节约空间复杂度
 //Time:O(n) Space:O(1)
 public static int solution2(int[] arrays){
 int num=0;
 for (int pre:arrays){
 num^=pre;
 }
 return num;
 }

 public static void main(String[] args) {
 int[] array=new int[]{1,1,2,3,3,3};
 System.out.println(solution2(array));
 }
}