問題
給定一個(gè)數(shù)組，只會存在一個(gè)不重復(fù)元素漱病，其余都為重復(fù)元素买雾。求不重復(fù)元素值。
思路
1）利用set自動去重杨帽，遍歷數(shù)組向set中添加漓穿，如果添加失敗，則代表出現(xiàn)重復(fù)元素注盈，則刪除該元素晃危。最終set中的值就是數(shù)組中的不重復(fù)元素。（該方式效率較低）
2）利用異或操作老客。
相異為真僚饭、相同為假。
任何數(shù)異或自身都為0沿量。
任何數(shù)異或0都為自身浪慌。
實(shí)現(xiàn)
1)set方式實(shí)現(xiàn)
public class SingleNumber {
public static void main(String[] args) {
int[] nums = new int[]{4,1,2,1,2};
System.out.println(singleNum1(nums));
}
private static int singleNum1(int[] nums) {
/**
* 首先不重復(fù)的元素在元素中只會存在一個(gè)
* 利用set自動去重，如果添加失敗朴则，代表存在权纤，則刪除這個(gè)元素。 最終存在的就是不重復(fù)的乌妒。
*/
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)){
//添加失敗
//刪除set中該元素
set.remove(num);
}
}
return (int)set.toArray()[0];
}
}
image.png
2）異或操作實(shí)現(xiàn)
public class SingleNumber {
public static void main(String[] args) {
int[] nums = new int[]{4,1,2,1,2};
System.out.println(singleNum2(nums));
}
private static int singleNum2(int[] nums) {
/**
* 異或運(yùn)算：
* 相異為真汹想，相同為假
* a^a=0 , a^0=a
* 任何數(shù)和相同值異或都為0
* 任何數(shù)和0異或都為自身
* 那么原數(shù)組可想象為： 4,1,1,2,2 = 4
*/
int result = 0;
for (int num : nums) {
result = result ^ num;
}
return result;
}
image.png
