對異或運算子的應用，非常有趣
——leetcode此題熱評
前言
哈嘍，大家好，我是一條，
糊涂演算法，難得糊涂，生命不息，刷題不止！
Question
難度：簡單
給定一個非空整數陣列，除了某個元素只出現一次以外，其余每個元素均出現兩次，找出那個只出現了一次的元素，
說明：
你的演算法應該具有線性時間復雜度， 你可以不使用額外空間來實作嗎？
示例 1:
輸入: [2,2,1] 輸出: 1示例 2:
輸入: [4,1,2,1,2] 輸出: 4
Solution
一條開始用hashSet做的，好家伙，足足
9ms后來看了一下原來有
異或運算這么神奇的方法
異或運算滿足以下規律：
- 交換律：a ^ b ^ c = a ^ c ^ b
- 任何數于0異或為任何數 0 ^ n = n
- 相同的數異或為0: n ^ n = 0
int a[] ={2,3,2,4,4};
2 ^ 3 ^ 2 ^ 4 ^ 4= 2 ^ 2 ^ 4 ^ 4 ^ 3 = 0 ^ 0 ^3 = 3
Code
所有
leetcode代碼已同步至github歡迎
star
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for (int i = 0; i < nums.length; i++) {
result =nums[i]^result;
}
return result;
}
}
Result
復雜度分析
- 時間復雜度：O(N)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289860.html
標籤：java
上一篇：面試官：說一下類加載的程序
下一篇：基于PyQT5實作垃圾分類小程式