LeetCode 进阶之路 - 136.只出现一次的数字

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

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

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


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

复制

我的脑子只想出暴力方法来解，看了题解后发现可以用位运算，真是巧妙。

/**
 * 136. 只出现一次的数字
 * @Author: lixj
 * @Date: 2020/9/21 10:19
 */
public class SingleNumber {
    /**
     * 暴力法
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        if (nums.length ==1) return nums[0];
        Arrays.sort(nums);
        if (nums[0] != nums[1]) return nums[0];
        if (nums[nums.length-1] != nums[nums.length-2]) return nums[nums.length-1];
        for (int i = 1; i < nums.length-1; i++) {
            if (nums[i-1] != nums[i] && nums[i] != nums[i+1]) {
                return nums[i];
            }
        }
        return 0;
    }

    /**
     * 位运算
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        int single = 0;
        for (int num : nums){
            single ^= num;
        }
        return single;
    }
    
    public static void main(String[] args) {
        int[] nums = new int[]{2,4,3,2,3};
//        int[] nums = new int[]{2,2,1};
//        int[] nums = new int[]{1};
        SingleNumber singleNumber = new SingleNumber();
        System.out.println(singleNumber.singleNumber1(nums));
    }
}

复制

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links:https://lixj.fun/archives/leetcode进阶之路-136只出现一次的数字