- 浏览: 174758 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
给定一个数组,里面有两个数字出现了一次,其他都出现了两次,找出这两个元素,要求在线性时间内完成。我们用位运算来完成,首先将数组中所有的元素进行异或运算得到一个值helper,然后用helper & (~(helper - 1)) 这样就得到了一个某一位为1其他位全为0的数tell,并且1所在的位上两个单独出现的数肯定不同。我们通过tell将数组中的元素分为两部分,分别与tell进行位与运算,最终得到两个单独的数。代码如下:
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
给定一个数组,里面有两个数字出现了一次,其他都出现了两次,找出这两个元素,要求在线性时间内完成。我们用位运算来完成,首先将数组中所有的元素进行异或运算得到一个值helper,然后用helper & (~(helper - 1)) 这样就得到了一个某一位为1其他位全为0的数tell,并且1所在的位上两个单独出现的数肯定不同。我们通过tell将数组中的元素分为两部分,分别与tell进行位与运算,最终得到两个单独的数。代码如下:
public class Solution { public int[] singleNumber(int[] nums) { if(nums == null || nums.length < 2) return new int[0]; int helper = 0; for(int i = 0; i < nums.length; i++) { helper ^= nums[i]; } int tell = helper & (~(helper - 1)); int single1 = 0; int single2 = 0; for(int i = 0; i < nums.length; i++) { if((nums[i] & tell) == 0) { single1 ^= nums[i]; } else { single2 ^= nums[i]; } } int[] result = {single1, single2}; return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 233You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 349Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 343Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 462Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 526Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 438Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 625Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 436The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 393Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 543Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 379All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 871Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 885Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 560Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 612Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 772Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 741You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
给喜欢算法的同学准备的Single Number调试用demo。
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 ...
Number(落单的数) 、 / Medium Single Number II(落单的数 II) 、 Medium Single Number III(落单的数 III) Medium Hash Function(哈希函数) Easy Space Replacement(空格替换) Easy Insert Interval Easy Two ...
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 ...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same ...Single Number ...Number ...Single Number III #274 H-Index #283 Move Zeroes #292 Nim Game #318 Maximum P
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
As each number is read, print it only if it is not a duplicate of a number already read. Prepare for the “worst case” in which all 20 numbers are different. Use the smallest possible array to solve...
We consider the problem of estimating detailed 3D structure from a single still image of an unstructured environment. Our goal is to create 3D models that are both quantitatively accurate as well as ...
parameters of single-frequency tones from a finite number of noisy discrete-time observations. The problem has application to data set testing, telephone transmission system testing, radar, and other ...
Deep Mixture density network for voice conversion. Single layer Multi Layer Perceptron Neural Network with desired number of mixure components.
As each number is read, print it only if it is not a duplicate of a number already read. Prepare for the “worst case” in which all 20 numbers are different. Use the smallest possible array to solve...
PAT甲级 1024 Palindromic Number A number that will be the same when it is written... All single digit numbers are palindromic numbers. Non-palindromic numbers can be paired with palindromic ones via a se
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.
Abs(number) 取得数值的绝对值。 Asc(String) 取得字符串表达式的第一个字符ASCII 码。 Atn(number) 取得一个角度的反正切值...CSng(expression) 转换表达式为Single 型态。 CStr(expression) 转换表达式为String 型
If you are a licensee of the “ASP.NET Version” of THE PRODUCT, then you are granted a license as a single individual to distribute THE PRODUCT royalty-free along with an unlimited number of ...
If you are a licensee of the “ASP.NET Version” of THE PRODUCT, then you are granted a license as a single individual to distribute THE PRODUCT royalty-free along with an unlimited number of ...
真正的量子随机数生成器。 该随机数生成器使用ANU Quantum随机数服务器。 此扩展提供了访问真正随机数的权限,并允许用户指定随机数的范围。 该扩展名中的随机数对于每个用户都是唯一的,并且可以安全地传输。...
matlab进行图形代码自然图像拼接中的单视角扭曲 该存储库是我们对 IEEE TIP 2019 论文《自然图像拼接中的单视角扭曲》的实现。...number={}, pages={724--735}, year={2020}, doi={10.1109/TIP.201
Can write a single register. Simple write multiple coils to a slave. Screen dump of communication traffic. You can save the data to a text file. Use the test center to compose your own strings ...
#定义 #nInput : Number of Neuron in input layer #nHide : Number of Neuron in hide layer #nOutput : Number of Neuron in output layer #studyspeed : Learning Rate network = NeuralNetWork(nInput = nInput...