[LeetCode] 136. Single Number* 解題思路 (Easy)

找出數字陣列中沒有重複的數字。

LeetCode 題目連結

 

https://leetcode.com/problems/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

Accept 作法

這題考的是把沒重複的數字返回，因為覺得利用 XOR 的方式最聰明省事，故保留此方法，但其實還有其他方法。趁機複習了一下位元運算。

XOR運算方式

0 XOR 0 0
0 XOR 1 1
1 XOR 0 1
1 XOR 1 0



Runtime: 0 ms
Memory: 40.1 MB

Java 程式碼

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

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題