iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
0
Software Development

LeetCode小試身手系列 第 8

【Day 8】#136 - Single Number

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

解析

此題要求從一陣列中找出非成對出現的數字。由於兩個同樣的位元進行XOR運算後會得到0,任何位元與0進行XOR運算後的值都是原值,因此如果有一遮罩的 bit 都是0,則某數與其進行XOR運算後會保持原值。基於這個原理,將陣列中所有的值都進行XOR運算後,最後得到的數字即為此題所求。

解法

class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<nums.length;i++){
            value^=nums[i];
        }
        return value;
    }
}

備註

Java的位元運算有以下四種:

  1. 補數運算(~):進行數值的2補數運算,如下:
     ~  0 1 0 1   運算元1
     =  1 0 1 1   (~運算元1)    –    回傳結果  
  1. AND(&):若兩者皆為1則輸出為1,否則輸出皆為0,如下:
        0 0 1 1   運算元1
   AND  1 0 0 1   運算元2
     =  0 0 0 1   (運算元1 & 運算元2)    –    回傳結果
  1. OR(|):若兩者有一個為1則輸出為1,兩者皆為0則輸出為0,如下:
        0 0 1 1   運算元1
    OR  1 0 0 1   運算元2
     =  1 0 1 1   (運算元1 | 運算元2)    –    回傳結果    
  1. XOR(^):若兩者位元不同則輸出為1,若相同則輸出為0,如下:
        0 0 1 1   運算元1
   XOR  1 0 0 1   運算元2
     =  1 0 1 0   (運算元1 ^ 運算元2)    –    回傳結果

希望透過記錄解題的過程,可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知,若有更好的解法也歡迎留言,謝謝。


上一篇
【Day 7】#1184 - Distance Between Bus Stops
下一篇
【Day 9】#79 - Word Search
系列文
LeetCode小試身手14

尚未有邦友留言

立即登入留言