数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++程序：寻找独特竞价游戏中的获胜者
假设我们有一个包含n个元素的数组A。有n个参与者，第i个参与者选择数字A[i]。竞价游戏的获胜者是选择的数字唯一且最小的参与者。我们必须找到获胜参与者的索引。如果不可能，则返回-1。
问题类别
编程中的各种问题可以通过不同的技术来解决。为了解决问题，我们首先必须设计一个算法，为此我们必须详细研究特定问题。如果同一个问题反复出现，可以使用递归方法；或者，我们也可以使用迭代结构。可以使用if-else和switch case等控制语句来控制程序中逻辑的流程。有效地使用变量和数据结构可以提供更简单的解决方案以及轻量级、低内存需求的程序。我们必须查看现有的编程技术，例如分治法、贪心算法、动态规划，并找出它们是否可行。这个问题我们可以通过一些基本的逻辑或暴力方法来解决。请遵循以下内容以更好地理解该方法。
因此，如果我们问题的输入类似于A = [2, 3, 2, 4, 2]，则输出将为1，因为选择了3的参与者可以赢得游戏。
步骤
为了解决这个问题，我们将遵循以下步骤：
Define one map cnt, and another map pos, both for integer type key and integer type value n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: x := A[i] increase cnt[x + 1] by 1 pos[x + 1] = i ans := -1 for each key-value pair it in cnt, do if value of it is same as 1, then: ans := pos[key of it] Come out from the loop return ans
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
map<int, int> cnt, pos;
int n = A.size();
for (int i = 0; i < n; i++){
int x = A[i];
cnt[x + 1]++;
pos[x + 1] = i;
}
int ans = -1;
for (auto it : cnt){
if (it.second == 1){
ans = pos[it.first];
break;
}
}
return ans;
}
int main(){
vector<int> A = { 2, 3, 2, 4, 2 };
cout << solve(A) << endl;
}输入
{ 2, 3, 2, 4, 2 }输出
1
更新于：2022年4月8日
264 次浏览
广告