在编程中,找出数组中不同的数字可以通过多种方法实现。以下是几种常见的方法及其思路:
方法一:异或运算
异或运算(XOR)具有以下性质:
1. 任何数和0做异或运算,结果仍然是原来的数,即 `a ^ 0 = a`。
2. 任何数和其自身做异或运算,结果是0,即 `a ^ a = 0`。
3. 异或运算满足交换律和结合律,即 `a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b`。
利用这些性质,可以找出数组中只出现一次的数字。
代码示例:
```cpp
include include void findUniqueNumbers(const std::vector int xor_result = 0; for (int num : nums) { xor_result ^= num; } // 找到最右边的第一个1 int n = 1; while ((xor_result & n) == 0) { n <<= 1; } num1 = 0; num2 = 0; for (int num : nums) { if (num & n) { num1 ^= num; } else { num2 ^= num; } } } int main() { std::vector int num1, num2; findUniqueNumbers(nums, num1, num2); std::cout << "The two unique numbers are: " << num1 << " and " << num2 << std::endl; return 0; } ``` 方法二:使用哈希表 如果需要找出多个不同的数字,可以使用哈希表来记录每个数字出现的次数,然后遍历哈希表找出只出现一次的数字。 代码示例: ```cpp include include include void findUniqueNumbers(const std::vector std::unordered_map for (int num : nums) { count_map[num]++; } for (const auto& pair : count_map) { if (pair.second == 1) { unique_nums.push_back(pair.first); } } } int main() { std::vector std::vector findUniqueNumbers(nums, unique_nums); std::cout << "The unique numbers are: "; for (int num : unique_nums) { std::cout << num << " "; } std::cout << std::endl; return 0; } ``` 方法三:排序后检查 如果数组是有序的,可以先对数组进行排序,然后检查相邻的元素是否相同,从而找出不同的数字。 代码示例: ```cpp include include include void findUniqueNumbers(std::vector std::sort(nums.begin(), nums.end()); int unique_nums = {nums, nums}; for (size_t i = 2; i < nums.size(); ++i) { if (nums[i] != nums[i - 1]) { unique_nums = nums[i]; break; } } std::cout << "The two unique numbers are: " << unique_nums << " and " << unique_nums << std::endl; } int main() { std::vector findUniqueNumbers(nums); return 0; } ``` 总结 以上方法各有优缺点,选择哪种方法取决于具体的需求和约束条件。异或运算方法时间复杂度为O(n),空间复杂度为O(1