給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1]
輸出: 1
示例?2:

輸入: [4,1,2,1,2]
輸出: 4

思路：拿map，set，都不符合要求。

map：

class Solution {public int singleNumber(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (Integer i : nums) {Integer count = map.get(i);count = count == null ? 1 : ++count;map.put(i, count);}for (Integer i : map.keySet()) {Integer count = map.get(i);if (count == 1) {return i;}}return -1; // can't find it.} }

我們知道什么數(shù)字和自己異或，都等于0.

什么數(shù)字和0異或，都等于它本身。

所以全部異或一遍，答案就是那個(gè)出現(xiàn)一次的數(shù)字。

class Solution {public int singleNumber(int[] nums) {int ans = 0;for(int i :nums)ans ^= i;return ans;} }

?

總結(jié)

以上是生活随笔為你收集整理的leetcode136 只出现一次的数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。