Leetcode advanced road - 136 A number that appears only once

 Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

 explain ：
 Your algorithm should have linear time complexity .  Can you do this without using extra space ？

 Example  1:
 Input : [2,2,1]
 Output : 1


 Example  2:
 Input : [4,1,2,1,2]
 Output : 4

Copy

My mind only thinks of violent solutions , After reading the solution, I found that bit operation can be used , That's clever .

/**
 * 136.  A number that appears only once 
 * @Author: lixj
 * @Date: 2020/9/21 10:19
 */
public class SingleNumber {
    /**
     *  Violence law 
     * @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;
    }

    /**
     *  An operation 
     * @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));
    }
}

Copy

Copyright: use Creative Commons signature 4.0 International license agreement to license Links:https://lixj.fun/archives/leetcode Advanced road -136 A number that appears only once