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

评论

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);