从今天起,每天坚持一道算法题,有时间就发到博客中,坚持!!!为了以后面试更从容。
先来一道简单的:
136. Single Number
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?
分析:题目很简单,给一个整型数组,其中一个数字出现一次,其它都是成对出现。找出单独出现的数字。
题目要求两点:1、线性时间复杂度;2、不要用额外的存储空间。
我们很容易想到,成对出现的数字相减等于0,所以只要成对相减完,剩下的就是单独出现的数字。
我能想到的最简单思路:
1、将数组排序,从大到小,从小到大均可;
2、设置步长为2,两两相减,等于0则调整步长,否则找到单独出现的数字;
3、收尾:若单独出现的数字出现在最后一个,直接返回。
代码如下:
public class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); int index = 0; while (index < nums.length - 1) { if (nums[index] - nums[index + 1] == 0) { index = index + 2; } else { return nums[index]; } } return nums[index]; } }
排序直接使用Arrays.sort,如果大家有其他更好思路,欢迎拍砖,谢谢!
相关推荐
颜色分类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 ...
136 | [Single Number](https://leetcode.com/problems/single-number/) | [C++](./C++/single-number.cpp) [Python](./Python/single-number.py) | _O(n)_ | _O(1)_ | Easy ||| 137 | [Single Number II]...
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ ...Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground ...Single Number 石头游戏 292. Nim Gam
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
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....
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 ...
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...
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 ...
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) 优化 ...
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
LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 3 简单的 7 简单的 9 简单的 22 中等的 26 简单的 27 Remove_Element ...136 ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_
Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 Maximum Depth of Binary Tree 这?也太简单了吧。。一行代码,一个尾递归搞定啊。。 终于想清楚了,leetcode的AC率应该是:在线编辑、...
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...