编程怎么找出不同的数字

时间:2025-01-23 18:21:32 游戏攻略

在编程中,找出数组中不同的数字可以通过多种方法实现。以下是几种常见的方法及其思路:

方法一:异或运算

异或运算(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& nums, int& num1, int& num2) {

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 nums = {1, 2, 3, 2, 1};

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& nums, std::vector& unique_nums) {

std::unordered_map count_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 nums = {1, 2, 3, 2, 1};

std::vector unique_nums;

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& nums) {

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 nums = {1, 2, 3, 2, 1};

findUniqueNumbers(nums);

return 0;

}

```

总结

以上方法各有优缺点,选择哪种方法取决于具体的需求和约束条件。异或运算方法时间复杂度为O(n),空间复杂度为O(1