当前位置:网站首页>Leetcode-136- number that appears only once (solve with XOR)
Leetcode-136- number that appears only once (solve with XOR)
2022-07-07 16:14:00 【_ Spring_】
Title Description
Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .
explain :
Your algorithm should have linear time complexity . Can you do this without using extra space ?
Example 1:
Input : [2,2,1]
Output : 1
Example 2:
Input : [4,1,2,1,2]
Output : 4
Tips: Solve with XOR
Basic knowledge of
The characteristic of XOR :
1. Law of constancy :A ^ 0 = A
2. Zero rate :A ^ A = 0
3. Commutative law :A ^ B = B ^ A
4. Associative law :(A ^ B) ^ C = A ^ (B ^ C)
Application point
You can judge whether the two values are equal by XOR :a ^ b == 0, be a And b equal .
Use XOR to eliminate numbers that appear twice
Their thinking
Use the zeroing rate of XOR , Make all the numbers that appear twice become 0, And the number and... That only appear once 0 The operation can still keep itself . Let's look at the following example .
Let's say all arrays are :abcbcda
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d
Code
Solution 1 :
My first spicy chicken solution , Leng find .
High time complexity , The last test case failed .
def singleNumber(nums):
"""
:type nums: List[int]
:rtype: int
"""
validated = []
for i, num in enumerate(nums):
if num in validated:
continue
single = True
for j in range(len(nums) - i - 1):
print(num, nums[j+i+1])
if num == nums[j + i + 1]:
validated.append(num)
single = False
if single:
print(num)
break
Solution 2 : Excellent algorithm :
def excellent_singleNumber(nums):
a = 0
for num in nums:
a ^= num
return a
It was amazing when I first saw this algorithm ……
Reference resources :
Leetcode-136- A number that appears only once
边栏推荐
- hellogolang
- There are many ways to realize the pause function in JS
- How to determine whether the checkbox in JS is selected
- Leetcode-136-只出现一次的数(用异或来解答)
- Learn good-looking custom scroll bars in 1 minute
- Limit of total fields [1000] in index has been exceeded
- 修改配置文件后tidb无法启动
- 2022第四届中国(济南)国际智慧养老产业展览会,山东老博会
- 如何在shell中实现 backspace
- 保证接口数据安全的10种方案
猜你喜欢
Three. JS introductory learning notes 07: external model import -c4d to JSON file for web pages -fbx import
讲师征集令 | Apache SeaTunnel(Incubating) Meetup 分享嘉宾火热招募中!
星瑞格数据库入围“2021年度福建省信息技术应用创新典型解决方案”
A wave of open source notebooks is coming
Xcode Revoke certificate
Three. JS introductory learning notes 03: perspective projection camera
JS array foreach source code parsing
SPI master RX time out interrupt
Apache Doris just "graduated": why should we pay attention to this kind of SQL data warehouse?
模仿企业微信会议室选择
随机推荐
招标公告:2022年云南联通gbase数据库维保公开比选项目(第二次)比选公告
A JS script can be directly put into the browser to perform operations
The inevitable trend of the intelligent development of ankerui power grid is that microcomputer protection devices are used in power systems
Excessive dependence on subsidies, difficult collection of key customers, and how strong is the potential to reach the dream of "the first share of domestic databases"?
121. The best time to buy and sell stocks
模仿企业微信会议室选择
Dotween -- ease function
ThinkPHP URL 路由简介
The unity vector rotates at a point
2022第四届中国(济南)国际智慧养老产业展览会,山东老博会
Enterprise log analysis system elk
three.js打造酷炫下雪效果
Odoo integrated plausible embedded code monitoring platform
Eye of depth (VII) -- Elementary Transformation of matrix (attachment: explanation of some mathematical models)
leetcode 241. Different ways to add parentheses design priority for operational expressions (medium)
Introduction to pyGame games
Three. JS introductory learning notes 15: threejs frame animation module
Numpy -- data cleaning
Xcode Revoke certificate
Three. Introduction to JS learning notes 17: mouse control of 3D model rotation of JSON file