137. Single Number II (M) (待学习)

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

题意

给定一个非空数组，该数组中除了一个元素只出现一次外，其余所有元素都出现了三次，找出该元素。

思路

1. 使用HashMap标记只出现一次的元素；
2. 先对数组排序，再找出只出现一次的元素；
3. 求出数组和sum2以及对应的Set集合的和sum1，则待求元素为 ；
4. 位运算:
   1. 对于int的32位，统计数组中所有数在每一位上“1”的个数，如果正好是3的倍数，说明目标元素x在对应位上为0；如果不是3的倍数，说明x在对应位上为1；
   2. 参考 LeetCode 137. 只出现一次的数字 II。

代码实现 - Map

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], true);
            } else {
                map.put(nums[i], false);
            }
        }
        for (Integer i : map.keySet()) {
            if (map.get(i) == false) {
                return i;
            }
        }
        return 0;
    }
}

代码实现 - 排序

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

代码实现 - Set求和

class Solution {
    public int singleNumber(int[] nums) {
        long sum1 = 0, sum2 = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            sum2 += nums[i];
            set.add(nums[i]);
        }
        for (int i : set) {
            sum1 += i;
        }
        return (int) ((sum1 * 3 - sum2) / 2);
    }
}

代码实现 - 位运算 1

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                ans = ans | (1 << i);
            }
        }
        return ans;
    }
}

代码实现 - 位运算 2

class Solution {
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            a = (a ^ nums[i]) & (~b);
            b = (b ^ nums[i]) & (~a);
        }
        return a;
    }
}