今天要挑战把一个阵列中,没有与自己相同的数字找出来,让我们一起来试看看吧!
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来达到,我们只要对题目给我们的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]
除了上述利用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 )
任天堂在经历了 NGC 的失败後、开始上上下下的进行检讨、得出了几个结论。 任天堂比起 SONY 或...
You are given a string s and an array of strings w...
来到铁人赛的最後一篇! 走到现在,人生中如果能学以致用,真的很幸福~虽然心中有过无数将网页开发结合到...
op.27 纪录时空间的情话 让我们彼此之间的记忆与美好时光 永恒纪载 今天来将 Broker 进...
元件介绍 Rate 是一个评分元件。一方面可以对於评价的数据展示,另一方面可以让人进行对评分的操作。...