LeetCode 137. 只出现一次的数字 II

137. 只出现一次的数字 II

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

说明:

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

示例1:

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

示例2:

输入: [0,1,0,1,0,1,99]
输出: 99

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 1. map映射

思路：
方法类似于 LeetCode 136. 只出现一次的数字 - 简书

复杂度分析：

• 时间复杂度：O(n + m) = O(n), 时间复杂度为两次遍历所用的时间

• 空间复杂度：O(n), map所需要的空间

• 2. 排序法

思路：

1. 先将数组进行排序
2. 遍历该数组，判断当前元素和下一个元素是否相等，如果不等，返回该数即可，否则继续向下遍历
3. 如果遍历到最后一个元素还没有找到出现一次的数字，则最后一个元素一定是我们需要的

public static int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i += 3) {
            if (i == nums.length - 1) return nums[i];
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return -1;
    }

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

• 3. 计数法

思路：使用(set去重后的元素之和 * 3 - 原数组之和) / 2 则为不重复的元素

public static int singleNumber(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        int sum = 0;
        int setSum = 0;
        for (int num : nums) {
            sum += num;
            set.add(num);
        }
        for (Integer i : set) {
            setSum += i;
        }
        return (setSum * 3 - sum) / 2;
    }

复杂度分析：

• 时间复杂度：O(n + s), 遍历数组和set所需的时间

• 空间复杂度：O(n), set所需的空间

• 测试用例

public static void main(String[] args) {
         int[] nums = {2, 2, 3, 2};
         System.out.println(Arrays.toString(nums));
         System.out.println("只出现一次的数字 II:" + singleNumber2(nums));
    }

• 结果

[2, 2, 3, 2]
只出现一次的数字 II:3

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github