升级版:
260. Single Number III
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?
分析:和前两篇的成对出现找出一个单独的数不同,本题需要找出两个单独的数,这里就有一个坑:若是成对的数出现,相减等于0,这没有问题;但相减不等于0 的两个数,一定就是要找的那两个单独的数吗?
答案肯定不是,因为这两个单独出现的数可以出现在排序后的头、尾或者中间,简单的用步长2相减,只可能找到一个,但下一个步长就乱了。
解决方案:1、排序;
2、若是两个数相减等于0,步长+2
3、若是两个数相减不等于0,步长+1,并记录第一个数,即第一个孤独数
4、若是最后还有数剩余,即为第二个孤独数。
5、返回结果
public class Solution { public int[] singleNumber(int[] nums) { Arrays.sort(nums); List<Integer> result = new ArrayList<Integer>(); int index = 0; while(index < nums.length - 1) { if (nums[index] - nums[index + 1] == 0) { index += 2; } else { result.add(nums[index]); index += 1; } } if (index < nums.length) { // 收尾 result.add(nums[index]); } Integer[] ret = (Integer[])result.toArray(new Integer[0]); return new int[]{ret[0].intValue(), ret[1].intValue()}; } }
相关推荐
颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 problems solved lintcode: 49 problems solved Title URL Solution Difficulty ...
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 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ ...Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两...
136_single_number.py # 位操作:异或(xor)操作 x ^ 0 = x; x ^ x = 0 sum 001_two_sum.py # 求list中能加和成指定值的两个位置 015_3_sum**.py # 求list中能加和成0的三个值 数列 004_median_of_two_sorted_arrays....
The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading ...
SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 ...
The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading ...
Single Number 52.2% Easy 371 两个整数的和 51.6% Easy 104 二叉树的最大深度 50.1% Easy 325% Add the Easy 389.数字 49.9% 简单 226 反转二叉树 48.9% 简单 283 移动零点 46.9% 简单 404 左叶总和 45.5% 简单 383...
https://leetcode.com/problems/single-number/ level : - easy tags : - recursive - linked list solutions : - reverseList - runtime : 52 ms, beats 99.80% - memory : 35 MB, beats 47.37% - ...
leetcode添加元素使和等于 LeetCode LeetCode Record 归并快排的区别: 思想不同:归并从局部到整体,快排从整体到局部 ...number. How? First, we need to understand the properties of XOR: firstly, XOR'
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
dna匹配 leetcode leetcode刷题--C++ ...Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 Maximum Depth of Binary Tree 这?也太简单了吧。。一行代码,一个尾递归搞定啊。。 终于想清楚了,leetcode的AC率应该是:在线编辑、...
LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 3 简单的 7 简单的 9 简单的 22 中等的 26 简单的 27 Remove_Element ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_
single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) ...
singleNumber ( self , nums : List [ int ]) -> int : 它是所谓的“类型提示”(或“函数注释”;自 Python 3.0 起可用)。 -> List[int] 意味着函数应该返回一个整数列表。 nums: List[int], target: int 表示 ...
number. 向后遍历数组,直到获得两个数的和是给定的值 You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single...