有一个由 n 个小于等于 10^9 的无序的正整数构成的数组,其中有且仅有一个数出现了一次,其他的数均出现了两次。请找出这个只出现一次的数。(用C++)
时间: 2024-05-08 13:21:06 浏览: 68
可以使用异或运算,因为异或运算满足结合律和交换律,相同的数异或结果为0,任何数与0异或结果为它本身。
具体思路是将所有数依次异或,最终的结果就是只出现一次的数。
下面是C++代码实现:
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int ans = 0; // 存储结果
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ans ^= x; // 异或运算
}
cout << ans << endl;
return 0;
}
```
时间复杂度为 O(n),空间复杂度为 O(1)。
相关问题
有一个由 n 个小于等于 10^9 的无序的正整数构成的数组,其中有且仅有一个数出现了一次,其他的数均出现了两次。请找出这个只出现一次的数。
可以使用异或运算来解决这个问题。将数组中所有的数进行异或操作,最终得到的结果就是只出现一次的数。
因为异或运算满足以下性质:
1. 任何数和 0 进行异或运算的结果仍为原数。
2. 任何数和自身进行异或运算的结果为 0。
3. 异或运算满足交换律和结合律。
因此,如果将数组中所有的数进行异或运算,那么出现两次的数都会被消掉,只留下只出现一次的数。
以下是示例代码:
```python
def find_single_num(nums):
result = 0
for num in nums:
result ^= num
return result
# 示例
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(find_single_num(nums)) # 输出 10
```
有一个无序的一维数组,里面有正有负 求子数组的和里面最大的那个和
这个问题可以使用动态规划来解决,时间复杂度为 O(n)。
定义两个变量:max_sum 和 cur_sum。max_sum 保存目前为止找到的最大子数组和,cur_sum 保存当前正在处理的子数组的和。
从数组的第一个元素开始,遍历数组。对于每个元素,将它加到 cur_sum 中。如果 cur_sum 变成了负数,说明当前的子数组不可能成为最大子数组的前缀,因此将 cur_sum 重置为0,从下一个元素开始重新计算子数组和。
每次计算出新的 cur_sum 后,将它和 max_sum 进行比较,如果 cur_sum 大于 max_sum,则更新 max_sum。
最后,返回 max_sum 即可。
下面是一个示例代码:
```
int maxSubArraySum(int arr[], int n)
{
int max_sum = arr[0];
int cur_sum = 0;
for (int i = 0; i < n; i++)
{
cur_sum += arr[i];
if (cur_sum > max_sum)
max_sum = cur_sum;
if (cur_sum < 0)
cur_sum = 0;
}
return max_sum;
}
```
阅读全文