只出现一次的数字优化算法

2018-06-05

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

1 2	输入: [2,2,1] 输出: 1

示例 2:

1 2	输入: [4,1,2,1,2] 输出: 4

思路：一开始能想到的是暴力方法，时间复杂度为O(N2)，超时，后来想到了先用排序算法对数组进行排序，然后找出和自身左右相邻的元素均不相等的元素即可，边界情况分情况讨论，此外还有数组只含有一个元素的特殊情况需要纳入考虑。采用插入排序即可通过该题，但是性能不如java提供的Arrays.sort的性能好，两种不同的实现方式的java代码如下：

Arrays.sort方式

class Solution {
    public int singleNumber(int[] nums) {
       
        int length=nums.length;
         if(length==1){
            return nums[0];
        }
        Arrays.sort(nums);
        
        int temp=0;
        if(nums[0]!=nums[1]){
            return nums[0];
        }
        if(nums[length-1]!=nums[length-2]){
            return nums[length-1];
        }
        
        for(int i=1;i<length-1;i++){
            if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]){
                temp=nums[i];
            }
        }
        return temp;
        
    }
}

插入排序方式：

class Solution {
    public int singleNumber(int[] nums) {
       
        int length=nums.length;
        if(length==1){
            return nums[0];
        }
        for(int i=1;i<length;i++){
            int insert=nums[i];
            int j;
            for(j=i-1;j>=0 && nums[j]>insert;j--){
                nums[j+1]=nums[j];
            }
            nums[j+1]=insert;
        }
        int temp=0;
        if(nums[0]!=nums[1]){
            return nums[0];
        }
        if(nums[length-1]!=nums[length-2]){
            return nums[length-1];
        }
        
        for(int i=1;i<length-1;i++){
            if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]){
                temp=nums[i];
            }
        }
        return temp;
        
    }
}