`
leonard1853
  • 浏览: 84521 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

LeetCode 136. Single Number

阅读更多

从今天起,每天坚持一道算法题,有时间就发到博客中,坚持!!!为了以后面试更从容。

 

先来一道简单的:

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,如果大家有其他更好思路,欢迎拍砖,谢谢!

2
1
分享到:
评论
1 楼 mrpanyu 2016-02-04  
有一种操作符叫“异或”:

int[] arr = new int[] { 6, 11, 7, 7, 60, 11, 6, 17, 21, 18, 60, 9, 82, 18, 21, 9, 82 };
int a = 0;
for (int i = 0; i < arr.length; i++) {
a = a ^ arr[i];
}
System.out.println(a);

相关推荐

    颜色分类leetcode-leetcode.etc:OJ、leetcode等解决方案

    颜色分类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 ...

    LeetCode最全代码

    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的Java代码

    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去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground ...Single Number 石头游戏 292. Nim Gam

    leetcode Single Number II - 位运算处理数组中的数 - 代金桥 - 博客园1

    扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出

    leetcode切割分组-leetcode:leetcode

    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:leetcode-java

    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和oj-leetCode:尝试一些OJ

    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...

    add-two-numbers

    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 ...

    LeetCode2 Add Two Numbers

    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 ...

    leetcode分类-LeetCode:LeetCode在线裁判C++

    SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 ...

    leetcode蓄水池JAVA-leetcode-with-[removed]:wrapped_gift:用各种解决方案和单元测试来练习Leetcode

    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添加元素使和等于 LeetCode LeetCode Record 归并快排的区别: 思想不同:归并从局部到整体,快排从整体到局部 ...number. How? First, we need to understand the properties of XOR: firstly, XOR'

    LeetCode:LeetCode解决方案

    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:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ ...Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    LeetCode:LeetCode题解

    LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 3 简单的 7 简单的 9 简单的 22 中等的 26 简单的 27 Remove_Element ...136 ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_

    leetcode答案-leetcode:leetcode

    Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 Maximum Depth of Binary Tree 这?也太简单了吧。。一行代码,一个尾递归搞定啊。。 终于想清楚了,leetcode的AC率应该是:在线编辑、...

    leetcode添加元素使和等于-LeetcodePractice:力码练习

    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 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4) ...

    leetcoderuntimeerrorjava-leetcode:面试准备的数据结构和算法

    singleNumber ( self , nums : List [ int ]) -&gt; int : 它是所谓的“类型提示”(或“函数注释”;自 Python 3.0 起可用)。 -&gt; List[int] 意味着函数应该返回一个整数列表。 nums: List[int], target: int 表示 ...

    leetcode双人赛-java_leetcode:java打印letcode

    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...

Global site tag (gtag.js) - Google Analytics