- 浏览: 172722 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given an 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?
给定一个数组,每个元素都出现了两次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素。我们可以采取位运算,两个相同的数异或结果为0,任何数异或0都为它本身,因此我们只需要将数组中的数全部进行异或运算最后的结果就是出现一次的数,这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
给定一个数组,每个元素都出现了两次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素。我们可以采取位运算,两个相同的数异或结果为0,任何数异或0都为它本身,因此我们只需要将数组中的数全部进行异或运算最后的结果就是出现一次的数,这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
public class Solution { public int singleNumber(int[] nums) { if(nums == null) return -1; int result = 0; for(int i = 0; i < nums.length; i++) result ^= nums[i]; return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 551Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
给喜欢算法的同学准备的Single Number调试用demo。
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up ... and a single number counts as a sum.) Your job is to solve this problem in general.
Single Number III Power of Two Missing Number Maximum Product of Word Lengths Bitwise AND of Numbers Range Power of Three Rectangle Area 数论 Happy Number Ugly Number Ugly Number II Super Ugly Number ...
The output will be a single number, the average (mean) of the closing balances for the twelve months. It will be rounded to the nearest penny, preceded immediately by a dollar sign, and followed by ...
A checksum is an algorithm that scans a packet of data and returns a single number. The idea is that if the packet is changed, the checksum will also change, so checksums are often used for detecting ...
260 | [Single Number III](https://leetcode.com/problems/single-number-iii/) | [C++](./C++/single-number-iii.cpp) [Python](./Python/single-number-iii.py) | _O(n)_ | _O(1)_ | Medium || 268| [Missing ...
Number(落单的数) 、 / Medium Single Number II(落单的数 II) 、 Medium Single Number III(落单的数 III) Medium Hash Function(哈希函数) Easy Space Replacement(空格替换) Easy Insert Interval Easy Two ...
Single Number #150 Evaluate Reverse Polish Notation #169 Majority Element #171 Excel Sheet Column Number #217 Contains Duplicate #226 Invert Binary Tree #237 Delete Node in a Linked List #238 Product ...
for i=1 to session("singlenumber")直到next是选择singlenumber(代表某科目的单选题数量)个单选题。 下面的代码实现了从数据库中随机不重复的选题: set rs=server.createobject("adodb.recordset") sql="select ...
for i=1 to session("singlenumber")直到next是选择singlenumber(代表某科目的单选题数量)个单选题。 下面的代码实现了从数据库中随机不重复的选题: set rs=server.createobject("adodb.recordset") sql="select ...
137. 只出现一次的数字 II使用hashMap来存储每个数字出现的次数public int singleNumber(int[] nums) {题解参考:h
各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 Permutations (交换 取子集两种方式...
只出现一次的数字 题目 给定一个非空整数数组,除了某个元素只出现一次之外,其余每个元素均出现两次。找出那个只出现了一次的元素。... def singleNumber(self, nums: List[int]) -> int: a = 0 for i in n
示例 2:输出:[-1,0]示例 3:输出:[1,0]vector<int> singleNumber(vector<int>& nums) {//先对所有数字
Single Number #0167 - Two Sum - Input Array is sorted #0189 - Rotate Array #0217 - Contains Duplicate #0242 - Valid Anagram #0243 - Shortest Word Distance #0246 - Strobogrammatic Number #0263 -
SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ANAGRAMS 7 COUNTING ELEMENTS 日 问题描述 问题和解决方案链接 Git 解决方案页面 8 Middle of the ...
示例 1:输入: [2,2,3,2]输出: 3示例 2:输入: [0,1,0,1,0,1,99]输出: 99int singleNumber(vector<in
dna匹配 leetcode leetcode刷题--C++ ...Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
// Mobile No can be a single number, list or csv string var mobileNo = "XXXXXXXXXX" ; var mobileNo = [ "XXXXXXXXXX" , "XXXXXXXXXX" , "XXXXXXXXXX" ] ; var mobileNo = "XXXXXXXXXX,XXXXXXXXXX,XXXXXXXXXX" ...