算法-只出现一次的数字集合

前言

仅记录学习笔记，如有错误欢迎指正。

题目

记录一道面试过的题目
题目如下：

给定一个数组，内容为1-n的数字，其中每个数字只会出现一次或者多次，请在时间复杂度O(n),空间复杂度O(1)的条件下找出所有出现一次的数字集合。

例子：

输入：
1, 2, 3, 4, 5, 4, 3, 2

输出: 5，1

解释:
1,5只出现一次

代码

之前好像见过，但是没用心记录。

 public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 4, 3, 2};List<Integer> result = findUniqueNumbers(nums);System.out.println("Unique numbers: " + result);}public static List<Integer> findUniqueNumbers(int[] nums) {List<Integer> result = new ArrayList<>();// 使用异或运算找到所有出现一次的数字int xor = 0;for (int num : nums) {xor ^= num;}// 找到异或结果中最低位的1int lowestBit = xor & -xor;// 根据最低位的1将数组分成两部分，分别进行异或运算int group1 = 0, group2 = 0;for (int num : nums) {if ((num & lowestBit) != 0) {group1 ^= num;} else {group2 ^= num;}}// 将出现一次的数字添加到结果列表中if (isUnique(group1, nums)) {result.add(group1);}if (isUnique(group2, nums)) {result.add(group2);}return result;}public static boolean isUnique(int num, int[] nums) {int count = 0;for (int n : nums) {if (n == num) {count++;}}return count == 1;}