给定一个长度为 nn 的整数数组 a1,a2,…,ana1,a2,…,an。 请你找到数组中只出现过一次的数当中最小的那个数。 输出找到的数的索引编号。 a1a1 的索引编号为 11,a2a2 的索引编号为 22,…,anan 的索引编号为 nn。c++
时间: 2024-02-15 13:03:22 浏览: 30
好的,以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int find_min_unique(vector<int>& arr) {
unordered_map<int, int> count;
for (int num : arr) {
count[num]++;
}
for (int i = 0; i < arr.size(); i++) {
if (count[arr[i]] == 1) {
return i + 1;
}
}
return -1; // 数组中没有只出现一次的数
}
int main() {
vector<int> arr = {2, 3, 2, 4, 5, 4, 6, 3};
cout << find_min_unique(arr) << endl; // 输出 5
return 0;
}
```
在上面的代码中,我们使用了 C++ 的 `unordered_map` 来实现哈希表。其中 `count[num]++` 表示将数字 `num` 出现的次数加1,如果 `num` 还没有在哈希表中出现过,则默认次数为0。最后,我们遍历数组,找到第一个出现次数为1的数,并返回其索引+1。如果没有这样的数,则返回-1。
相关问题
给定一个长度为 nn 的整数数组 a1,a2,…,ana1,a2,…,an。 请你找到数组中只出现过一次的数当中最小的那个数。 输出找到的数的索引编号。 a1a1 的索引编号为 11,a2a2 的索引编号为 22,…,anan 的索引编号为 nn。
好的,这是一个简单的问题,可以使用哈希表来解决。我们遍历整个数组,统计每个数出现的次数,然后再遍历一遍数组,找到第一个出现次数为1的数即可。
以下是 Python 代码实现:
```python
def find_min_unique(arr):
count = {}
for num in arr:
count[num] = count.get(num, 0) + 1
for i, num in enumerate(arr):
if count[num] == 1:
return i + 1
return -1 # 数组中没有只出现一次的数
# 测试
arr = [2, 3, 2, 4, 5, 4, 6, 3]
print(find_min_unique(arr)) # 输出 5
```
在上面的代码中,我们使用了 Python 的字典来实现哈希表,其中 `count[num] = count.get(num, 0) + 1` 表示将数字 `num` 出现的次数加1,如果 `num` 还没有在字典中出现过,则默认次数为0。最后,我们遍历数组,找到第一个出现次数为1的数,并返回其索引+1。如果没有这样的数,则返回-1。
给定一个长度为 nn 的数组 a1,a2,…,ana1,a2,…,an。 现在,要将该数组从中间截断,得到三个非空子数组。 要求,三个子数组内各元素之和都相等。 请问,共有多少种不同的截断方法?
这是一个比较经典的问题,可以用前缀和的思想来解决。
首先,计算出整个数组的元素之和 sum,若 sum 不是 3 的倍数,则无法分割成三个和相等的子数组,直接返回 0。
然后,从左往右遍历数组,用一个变量 curSum 记录当前遍历到的位置之前的元素之和,若 curSum 为 sum/3,则在当前位置前面的子数组中选取一个截断点,得到第一个子数组;若 curSum 为 2*sum/3,则在当前位置前面的子数组中选取一个截断点,得到第二个子数组;最后,若当前位置是 n-1,则得到第三个子数组。注意,对于每个子数组,只有在下一个子数组确定之前才能进行选择截断点的操作,否则会出现重复计数的情况。
具体实现可以参考下面的 Python 代码:
```python
def countWays(nums):
n = len(nums)
if sum(nums) % 3 != 0:
return 0
cnt = 0
curSum = 0
firstSum = sum(nums) // 3
secondSum = 2 * firstSum
firstCount = [0] * n
secondCount = [0] * n
for i in range(n):
curSum += nums[i]
if curSum == firstSum:
firstCount[i] = 1
if curSum == secondSum:
secondCount[i] = 1
for i in range(1, n):
firstCount[i] += firstCount[i-1]
secondCount[i] += secondCount[i-1]
curSum = 0
for i in range(n-1):
curSum += nums[i]
if curSum == secondSum:
cnt += firstCount[i-1] * (secondCount[n-2] - secondCount[i-1])
return cnt
```
这个算法的时间复杂度为 O(n),空间复杂度也为 O(n)。