LeetCode 260. Single Number III

升级版：

 

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:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. 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()};
    }
}