題目描述

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解析：該題目暴力求解當然是可以通過的，但是不滿足題目的要求，題目要求時間復雜度為O（n）。

代碼一：暴力求解，不建議

import java.util.*; public class Solution {public int singleNumber(int[] A) {List<Integer> list = new ArrayList<>();for(int i:A){list.add(i);}Set<Integer> set = new HashSet<>(list);for(int i:set){int temp =i;int count=0;for(int j:A){if(j==i){count++;}}if(count==1){return temp;}}return -1;} }

代碼二：利用異或的計算特點。
1）相同的數異或為0,例如 6^6=0；
2）0異或不為0的數為不為0的數，例如：0^5=5

public static int singleNumber(int[] A) {int num = 0;for(int i=0;i<A.length;i++){num^=A[i];}return num; }

總結

以上是生活随笔為你收集整理的《leetcode》single-number的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。