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?

Analysis: 需求里面要求O(N)時間以及無額外空間，這就排除了使用boolean array, hashmap這些個方法，只能在原數組上進行查找。O(N)基本上就相當于遍歷數組.

最好的方法：

1 public class Solution { 2 public int singleNumber(int[] nums) { 3 int res = 0; 4 for(int i = 0 ; i < nums.length; i++){ 5 res ^= nums[i]; 6 } 7 return res; 8 } 9 }

第二遍做法： 17行 & 運算符優先等級低于 == 所以一定要打括號

1 public class Solution { 2 public int singleNumber(int[] A) { 3 int[] check = new int[32]; 4 int res = 0; 5 for (int i=0; i<A.length; i++) { 6 for (int j=0; j<32; j++) { 7 if ((A[i]>>j & 1) == 1) { 8 check[j]++; 9 } 10 } 11 } 12 for (int k=0; k<32; k++) { 13 if (check[k] % 2 == 1) { 14 res |= 1<<k; 15 } 16 } 17 return res; 18 } 19 }

一樣的思路另一個做法：

1 public int singleNumber(int[] A) { 2 int[] digits = new int[32]; 3 for(int i=0;i<32;i++) 4 { 5 for(int j=0;j<A.length;j++) 6 { 7 digits[i] += (A[j]>>i)&1; 8 } 9 } 10 int res = 0; 11 for(int i=0;i<32;i++) 12 { 13 res += (digits[i]%2)<<i; 14 } 15 return res; 16 }

?另外注意位運算符的優先級等級：

1 ()?[]?. 從左到右 2 !?+(正) ?-(負)?~?++?-- 從右向左 3 *?/?% 從左向右 4 +(加)?-(減) 從左向右 5 <<?>>?>>> 從左向右 6 <?<=?>?>=?instanceof 從左向右 7 ==?? != 從左向右 8 &(按位與) 從左向右 9 ^ 從左向右 10 | 從左向右 11 && 從左向右 12 || 從左向右 13 ?: 從右向左 14 =?+=?-=?*=?/=?%=?&=?|=?^= ?~= ?<<=?>>=?? >>>= 從右向左

轉載于:https://www.cnblogs.com/EdwardLiu/p/3795723.html

總結

以上是生活随笔為你收集整理的Leetcode: Single Number的全部內容，希望文章能夠幫你解決所遇到的問題。

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