首页 > Windows开发 > 详细

Acwing3764 唯一最小数

时间:2021-07-09 12:53:53      阅读:16      评论:0      收藏:0      [点我收藏+]

题目描述

给定一个长度为 n 的整数数组,找到数组中只出现过一次的数当中最小的那个数,输出它的下标。如果不存在,输出-1。
原题链接:https://www.acwing.com/problem/content/description/3764/

解法

读入的时候记录ai出现的次数,再扫一遍对出现次数为1的数更新最小值即可,每组数据的复杂度均为O(n)。

注意:不要使用下面被注释掉的memset,它每次都会作用于N个数,导致TLE。而应使用循环赋值。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, t, n, ans, num; 
int a[N], b[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		ans = N, num = -1;
		//memset(a, 0, sizeof(a));
		//memset(b, 0, sizeof(b));
		for (int i = 1; i <= n; i++) a[i] = b[i] = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			b[a[i]] ++;
		}
		for (int i = 1; i <= n; i++) {
			if (b[a[i]] == 1 && a[i] < ans) ans = a[i], num = i;
		}
		printf("%d\n", num);	
	} 
  return 0;
}

Acwing3764 唯一最小数

原文:https://www.cnblogs.com/vv123/p/14988601.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!