⑩给定一个包含 [0, n] 中 n 个数的数组 nums ⑪找出 [0, n] 这个范围内没有出现在数组中的那个数
时间: 2024-05-06 07:15:22 浏览: 18
可以使用哈希表或者异或操作来解决这个问题。
方法一:哈希表
我们可以使用一个哈希表,遍历数组 nums 中的每一个数,将其加入哈希表中。然后再遍历 [0, n] 这个范围内的所有数,如果某个数不在哈希表中,那么该数就是缺失的数。
方法二:异或操作
我们知道,异或操作具有自反性和结合律,即 a^b^b=a 和 a^b^c=a^c^b。因此,我们可以先将 [0, n] 中的所有数以及数组 nums 中的所有数进行异或操作,然后得到的结果就是缺失的数。
具体实现可以如下:
```python
# 方法一:哈希表
def findMissingNumber(nums):
hash_set = set(nums)
n = len(nums)
for i in range(n+1):
if i not in hash_set:
return i
# 方法二:异或操作
def findMissingNumber(nums):
res = len(nums)
for i in range(len(nums)):
res ^= i ^ nums[i]
return res
```
以上两种方法的时间复杂度均为 O(n),空间复杂度分别为 O(n) 和 O(1)。
相关问题
python实现给定一个包含[0,n]中 n 个数的数组 nums,找出[0,n]这个范围内没有出现在 数组的那个数
:你可以使用异或运算来解决这个问题。首先将数组中的所有数与从 1 到 n 的所有数进行异或操作,得到的结果就是缺失的那个数。
例如:
nums = [0, 1, 3, 4, 5, 6]
n = 6
missing = n ^ (nums[0] ^ nums[1] ^ ... ^ nums[n-1])
missing = 2
因为缺失的数为 2。
C语言编程给定一个数组,找出一个出现次数大于n/2的数
可以使用摩尔投票算法(Moore Voting Algorithm)来解决这个问题,时间复杂度为 O(n)。
算法思想如下:
1. 假设数组中第一个数出现次数为 1,将其设为候选数。
2. 从数组的第二个数开始遍历,如果当前数等于候选数,则将计数器加一,否则将计数器减一。
3. 如果计数器为 0,则将当前数设为候选数。
4. 最终留下的候选数即为出现次数大于 n/2 的数。
下面是 C 语言实现代码:
```c
int find_majority(int* nums, int nums_size) {
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums_size; i++) {
if (nums[i] == candidate) {
count++;
} else {
count--;
if (count == 0) {
candidate = nums[i];
count = 1;
}
}
}
return candidate;
}
```
该函数接收一个整型数组和数组长度作为参数,返回出现次数大于 n/2 的数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)