Leetcode 挑战 Day 05 [136. Single Number]

136. Single Number


今天要挑战把一个阵列中,没有与自己相同的数字找出来,让我们一起来试看看吧!

题目


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 1:

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

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

Input: nums = [1]
Output: 1

这题的意思比较简单明了,就是题目会给我们一个阵列,之中存的是整数,并且恰好会只有一个数是自己单独出现,其他都会成对出现的,我们必须找到那个数,而且是在big O(n)的时间复杂度内

HashMap


这题同样可以通过HashMap来达到,我们只要对题目给我们的List跑一次回圈,确认走访到的元素是否在HashMap之中,如果不在我们便将其放进去,如果在的话表示他已经出现过了,我们就把HashMap中的那个元素拿掉,回圈跑完後,还待在HashMap中的Key就是我们要的答案了。
而因为HashMap的查找和删除,时间复杂度都是O(1),因此我们可以确保这符合题目要求的线性复杂度。

以下为python3的程序码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count_dic = {}  
        for i in nums:  #O(n)
            if i in count_dic: # O(1) (HsahMap)
                del count_dic[i] 
            else:
                count_dic[i] = 1
                
        return [key for key in count_dic][-1]

XOR


除了上述利用HashMap能达到O(n)的复杂度,还可以用更特别的方法。在电脑运算中,有一种逻辑运算是XOR,概念上就是exclusive的OR,比较贴近生活上我们讲的或,只能有一个条件是True的时候才会输出True。

当然在这题上我们只需要知道他的应用性在於,自己XOR自己一定是0,而0 XOR任何数都会是那个任何数,透过这样的概念我们只要对阵列中每个元素逐一进行XOR运算,到最後的结果必定会是个数是一的数,最主要原因是其他重复出现的元素正好只会出现两次。

在以下程序码中,这个^符号代表XOR的运算。

以下是C++的程序码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++)
            res ^= nums[i];
        
        return res;
    }
};

<<:  [Day8] Flutter - 显示文字元件 ( Text )

>>:  [Day 8] .Net Task 底层(1)

Day-22 创新才是正义!带领任天堂重返荣耀的 Wii

任天堂在经历了 NGC 的失败後、开始上上下下的进行检讨、得出了几个结论。 任天堂比起 SONY 或...

(Hard) 30. Substring with Concatenation of All Words

You are given a string s and an array of strings w...

所学跟工作结合时---我用JS画了12个班级的座位表

来到铁人赛的最後一篇! 走到现在,人生中如果能学以致用,真的很幸福~虽然心中有过无数将网页开发结合到...

op.27 《全领域》-全域开发实战 - 居家植物盆栽 Mvt II (C# Broker & Mysql)

op.27 纪录时空间的情话 让我们彼此之间的记忆与美好时光 永恒纪载 今天来将 Broker 进...

【Day08】数据输入元件 - Rate

元件介绍 Rate 是一个评分元件。一方面可以对於评价的数据展示,另一方面可以让人进行对评分的操作。...