iT邦幫忙

2021 iThome 鐵人賽

DAY 24
0
自我挑戰組

30天 Leetcode解題之路系列 第 24

Day 24 - Single Number

大家好,我是毛毛。ヾ(´∀ ˋ)ノ
廢話不多說開始今天的解題Day~


136. Single Number

Question

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.


Example

Example1

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

Example2

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

Example3

Input: nums = [1]
Output: 1

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • 3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

解題

題目

首先先簡單的翻譯一下題目
給一組陣列,要找出其中只出現過一次的數字,其餘的每個數字只會出現兩次。

Think

作法大致上是這樣

  • 用一個dictionary存每個數字出現的次數,最後再去看是哪一個key的值是1
  • C的做法,因為後來發現我漏看題目XD,其他的數字都是出現兩次,如果用XOR的邏輯的話,相同的值回傳0,相異值回傳1,這樣最後剩下來的值,就是只出現一次的數字,其他出現兩次的都會變成0。

Code

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dict = {}
    
        for num in nums:
            if num not in dict:
                dict[num] = 1
            else:
                dict[num] += 1

        for key in dict:
            if dict[key] == 1:
                return key         

C

int singleNumber(int* nums, int numsSize){
    int ans = 0;
    
    for (int index=0 ; index<numsSize ; index++) {
        // printf("\nBefore: %p\n", ans);
        ans ^= nums[index];
        // printf("After: %p\n", ans);
    }
    
	return ans;
}

Result

  • Python

  • C

大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 23 - Keyboard Row
下一篇
Day 25 - Permutations
系列文
30天 Leetcode解題之路30

尚未有邦友留言

立即登入留言