首页 > 试题广场 >

Be Unique (20)

[编程题]Be Unique (20)
  • 热度指数：2996 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104 ]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.

输入描述:
Each input file contains one test case.  Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets.  The numbers are separated by a space.


输出描述:
For each test case, print the winning number in a line.  If there is no winner, print "None" instead.
示例1

输入

7 5 31 5 88 67 88 17

输出

31
算法知识视频讲解
添加回答
推荐
orgcheng头像 orgcheng
最直接的思路是：读取数据，存储到数组中，然后判断每个数值出现的次数。
因此该方法的时间复杂度是O(N^2)

如果使用哈希表记录读取数值和出现的次数，
那么每次就可以判断新读取的数值是否出现过。
如果没有，那就加入哈希表中，并记录出现的次数为1；
如果出现过，就更新出现的次数。

如果每次读取数据时，就判断其在当前是否为第一次出现。
是，那么就有可能是所要的答案，但是不一定，因为后面可能还会出现该值。
此时就可以把该值加入链表中，该链表存储可能的结果。

最后遍历链表，查找出第一个只在哈希表中出现一次的值就是结果，如果没有返回None。
下面是该方法的实现：时间复杂度O(N)
import java.io.PrintStream;
import java.text.ParseException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static Scanner in = new Scanner(System.in);
	public static PrintStream out = System.out;

	public static void main(String[] args) throws ParseException {
		int N = in.nextInt();
		int bet;

		// list存储可能的结果值
		List<Integer> list = new LinkedList<>();
		HashMap<Integer, Integer> map = new HashMap<>();

		for (int i = 0; i < N; ++i) {
			bet = in.nextInt();
			Integer val = map.get(bet);
			if (val == null) {
				map.put(bet, 1);
				list.add(bet);
			} else {
				map.put(bet, val + 1);
			}
		}

		// 检测list存储的值是否符合要求
		boolean findWinner = false;
		for (int i = 0; i < list.size(); ++i) {
			if (map.get(list.get(i)) == 1) {
				out.println(list.get(i));
				findWinner = true;
				break;
			}
		}
		if (!findWinner) {
			out.println("None");
		}
	}
}


编辑于 2015-08-18 22:22:08 回复(0)
SKT.RUO头像 SKT.RUO 
#include<stdio.h>
int main()
{
	int n, flag = 0, i, a[100005], num[100005] = {};
	scanf("%d", &n);
	for (i = 0;i < n;i++)
	{
		scanf("%d", &a[i]);
		num[a[i]]++;
	}
	for (i = 0;i < n;i++)
	{
		if (num[a[i]] == 1)
		{
			flag = 1;
			printf("%d", a[i]);
			break;
		}
	}
	if (flag == 0)
		printf("None");
	return 0;
}
看错了空间，蠢得要死。

发表于 2017-08-06 22:15:18 回复(0)
hustsun头像 hustsun 
#include <cstdio>
const int maxn = 100005;
int hashmap[maxn] = {0};

int order[maxn];
int main(void){
    int n;
    scanf("%d", &n);
    for(int j = 0; j < n; j++){
        int tmp;
        scanf("%d", &tmp);
        hashmap[tmp]++;
        order[j] = tmp;
    }
    int i;
    for(i = 0; i < n; i++){
        if(hashmap[order[i]] == 1){
            printf("%d", order[i]);
            break;
        }
    }
    if(i == n) printf("None\n");
    return 0;
}

发表于 2018-02-08 12:43:40 回复(0)
coco2009头像 coco2009 
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[10005];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){cin>>a[i];++b[a[i]];}
	for(int i=1;i<=n;++i)
		if (b[a[i]]==1){cout<<a[i]<<endl;return 0;}
	cout<<"None"<<endl;
	return 0;
}

发表于 2020-05-17 15:47:01 回复(0)
风蚀流云头像 风蚀流云 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int arr[N*10],mp[N];
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
        mp[arr[i]]++;
    }
    int flag = 1;
    for(int i = 0; i < n; i++){
        if(mp[arr[i]]==1){
            printf("%d\n",arr[i]);
            flag = 0;
            break;
        }
    }
    if(flag) printf("None\n");
    return 0;
}

发表于 2019-04-29 07:57:21 回复(0)
成为offer收割机1头像 成为offer收割机1

import java.io.;
import java.util.Scanner;
/*

  • 首先定义两个数组
  • 第一个数组进行数字存储
  • 第二个数组进行存储数字n出现的次数
  • 遍历数组如果只出现一个就打印并退出程序
  • 如果遍历程序后没有结果那就打印None

  • */
    public class Main {

    public static void main(String[] args) throws IOException
    {

     Scanner read=new Scanner(System.in);
 int n=read.nextInt();
 int [] num=new int[100005];
 int [] a=new int[100005];
 for(int i=0;i<n;i++)
 {
     num[i]=read.nextInt();
     a[num[i]]++;
 }
 for(int i=0;i<n;i++)
 {
     if(a[num[i]]==1)
     {
         System.out.println(num[i]);
         return;

     }
 }
 System.out.println("None");

    }
    }

发表于 2018-09-29 16:28:24 回复(0)
C/C++
一个好听的名字头像 一个好听的名字 
#include <iostream>
using namespace std;
int main()
{
    int n = 0;
    int a[100001] = {0};    //存出现次数
    int b[100001] = {0};   //存输入顺序的不同的数字
    int temp = 0, i = 0, j = 0;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> temp;
        if (a[temp] == 0)    //当这个数没有出现过时，就写入b
        {
            b[j] = temp;
            j++;
        }        
        a[temp]++;    //该数为下标的次数加一
    }
    for (i = 0; i < j; i++)    //按照输入的顺序来判断输入的数据
    {
        if (a[b[i]] == 1)      //快速索引，定位是否有为1的独特值
        {
            cout << b[i];
            break;
        }
    }
    if (i == j)   //判断不存在的情况
    cout << "None";
    return 0;
}

发表于 2018-08-19 20:49:26 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream>

using namespace std;

int main()
{     int N,a[100007],c[100007]={0};     bool flag=false;     cin>>N;     for(int i=0;i<N;i++)     {         cin>>a[i];         c[a[i]]++;     }     for(int i=0;i<N;i++)     {         if(c[a[i]]==1)         {             cout<<a[i]<<endl;             flag = true;             break;         }     }     if(!flag)         cout<<"None"<<endl;     return 0;
}

发表于 2018-03-09 01:00:04 回复(0)
C/C++
Myhui头像 Myhui 
#include <iostream>
using namespace std;

int main(){
    int x,i;
    int a[10010]={0},b[100010];
    cin>>x;
    for(i=0;i<x;i++){
        cin>>b[i];
        a[b[i]]++;
    }
    for(i=0;i<x;i++){
        if(a[b[i]]==1){
            cout<<b[i];
            break;
        }
    }
    if(i==x)cout<<"None";
    return 0;
}
发表于 2018-01-25 23:17:27 回复(0)
C/C++
likewind头像 likewind 
#include<cstdio> 
//C短短的20行左右的代码，综合的想                            法就是位图排序
#define MAX 999999
int arr[MAX];
int flag[MAX] = {0};
int total;
int main()
{
    scanf("%d", &total);
    for(int i = 0; i<total; i++)
    {
        scanf("%d", &arr[i]);
        flag[arr[i]]++;
    }
    for(int i = 0; i<total; i++)
    {
        if(flag[arr[i]] == 1){
            printf("%d", arr[i]);
            return 0;
        }
    }
    printf("None");
    return 0;
}
编辑于 2017-02-13 10:06:37 回复(1)
Chimney头像 Chimney
没看到题目说数字在10000以下，以为是输入整型所以第一时间排除了count数组的方法。。。
Hash的话有想过，但是c里面个人水平有限觉得费力气写那个划不来就没走这条路
我用的是二叉排列树存储输入，并且加了个bool型作remove标记（本来是读到第二次就删除节点这样树小点不至于效率太低，结果测试点告诉我我太蠢了这样的话输入奇数次时因为偶数次把原节点删了算法认为最后次是第一次输入导致错误），全部输入完成后统一进行节点删除。
这样的问题是删除节点会导致节点位置变化，根节点不一定是最先输入的，所以还需要对输入数字依次查找数字是否在树里
时间复杂度O(N)*O(h)，Hash冲突少的话应该没有Hash效率高，但其实N+k*O(h),树高h比较低、数字次序k靠前的话效率还是挺高的，平均时间复杂度应该也有O(N),如果N很大的情况，愿意花力气去写把最后的树调整成平衡二叉树的话效率会大幅度提高 
#include <iostream>
using namespace std;

#define LEFT true
#define RIGHT false

typedef struct sNode {
	int value;
	bool remove;
	sNode *l, *r;

	sNode() { l = r = NULL;remove = false; }
	sNode(int v) :value(v) { l = r = NULL;remove = false; }
}Tree;

void del(sNode* &node, sNode* parent, bool left) {
	sNode* d;
	if (parent) {
		if (!node->r) {
			if (left)parent->l = node->l;
			else parent->r = node->l;
			delete node;
			node = NULL;
		}
		else if (!node->l) {
			if (left)parent->l = node->r;
			else parent->r = node->r;
			delete node;
			node = NULL;
		}
		else {
			sNode* p = node;
			d = node->r;
			while (d->l) {
				p = d;
				d = d->l;
			}
			node->value = d->value;
			node->remove = d->remove;
			if (p - node)del(d, p, LEFT);
			else del(d, p, RIGHT);
		}
	}
	else {
		if (!node->r) {
			d = node;
			node = node->l;
			delete d;
			d = NULL;
		}
		else if (!node->l) {
			d = node;
			node = node->r;
			delete d;
			d = NULL;
		}
		else {
			sNode* p = node;
			d = node->r;
			while (d->l) {
				p = d;
				d = d->l;
			}
			node->value = d->value;
			node->remove = d->remove;
			if (p - node)del(d, p, LEFT);
			else del(d, p, RIGHT);
		}
	}
}

void remove(Tree* &tree,sNode* parent,bool left) {
	while (tree && tree->remove)del(tree, parent, left);
	if (tree) {
		if (tree->l)remove(tree->l, tree, LEFT);
		if (tree->r)remove(tree->r, tree, RIGHT);
	}
}

bool insert(sNode* node, Tree* tree) {
	if (node->value == tree->value) {
		tree->remove = true;
		return false;
	}
	else if (node->value < tree->value)
		if (tree->l)insert(node, tree->l);
		else tree->l = node;
	else
		if (tree->r)insert(node, tree->r);
		else tree->r = node;
	return true;
}

bool inIt(int num, Tree* tree) {
	if (!tree)return false;
	if (tree->value == num)return true;
	if (tree->value > num)return inIt(num, tree->l);
	else return inIt(num, tree->r);
}

void del(Tree* &tree) {
	if (!tree)return;
	del(tree->l);
	del(tree->r);
	delete tree;
	tree = NULL;
}

int main(int argc, const char* argv[]) {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int* num = new int[N];
	Tree* tree = NULL;
	for (int read, i = 0;i < N;i++) {
		cin >> read;
		num[i] = read;
		sNode* node = new sNode(read);
		if (!tree)tree = node;
		else insert(node, tree);
	}

	remove(tree, NULL, true);
	if (!tree)cout << "None";
	else for(int i=0;i<N;i++)
			if (inIt(num[i], tree)) {
				cout << num[i];
				break;
			}

	del(tree);
	delete[] num;
	//system("pause");
	return 0;
}

编辑于 2017-02-08 00:04:16 回复(1)
多米@璟头像 多米@璟 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int[] count=new int[10001];
		ArrayList<Integer> a=new ArrayList<Integer>();
		while(n-->0){
			int t=in.nextInt();
			a.add(t);
			count[t]++;
		}
		Iterator<Integer> it=a.iterator();
		while(it.hasNext()){
			int t=it.next();
			if(count[t]!=1)
				continue;
			else{
				System.out.println(t);
				return;
			}
		}
		System.out.println("None");
	}
}

发表于 2017-01-24 14:54:10 回复(0)
Python
0x100000001b3头像 0x100000001b3 
from collections import Counter
a = raw_input().split()[1:]
b = filter(lambda x:x[1] == 1, Counter(a).items())
print "None" if len(b) == 0 else sorted(b, key=lambda x:a.index(x[0]))[0][0]

发表于 2017-01-18 00:28:54 回复(0)
C/C++
猫猫猫1头像 猫猫猫1 
#include<bits/stdc++.h>
using namespace std;

int hashtable[10010];

int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		hashtable[a[i]]++;
	}
	bool flag=0;
	for(int i=0;i<n;i++){
		if(hashtable[a[i]]==1){
			printf("%d\n",a[i]);
			flag=1;
			break;
		}
	}
	if(!flag){
		printf("None\n");
	}
	return 0;
}

发表于 2022-11-11 10:05:33 回复(0)
hhhhh.头像 hhhhh.
终于争气了一回！！代码不复杂了QAQ 
#include <iostream>
using namespace std;

const int maxn = 100001;

int bet[maxn];
int num[maxn] = {0};

int main(){
    int n;

    int flag = 0;
   
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> bet[i];
        num[bet[i]]++;
    }
    
    for(int i = 0;i < n;i++){
        if(num[bet[i]] == 1){
            cout << bet[i];
            flag = 1;
            break;
        }
    }
    
    if(flag == 0){
        cout << "None";
    }
    return 0;
    
}


发表于 2019-09-02 16:48:25 回复(0)
Disconnect头像 Disconnect 
from collections import Counter
lst = list(map(int,input().split()[1:]))
con = Counter(lst)
boo = True
for i in lst:
    if con[i]==1:
        print(i)
        boo = False
        break
if boo:
    print('None')

发表于 2018-12-05 12:35:33 回复(0)
Java
yigexiaocainiao头像 yigexiaocainiao 
import java.util.*; public class Main{ public static void main(String[] args){
        Scanner sc = new Scanner(System.in);  while (sc.hasNext()){
            num[] a = new num[10001];  for (int i = 0;i<a.length;i++) {
                a[i] = new num(0,-1);  } int n = sc.nextInt();  for (int i = 0;i<n;i++){ int t = sc.nextInt();  a[t].number++;  if (a[t].time<0)a[t].time = i;  } int ans = -1;  num temp = new num(-1,Integer.MAX_VALUE);  for (int i = 1;i<a.length;i++){ if (a[i].number == 1 && a[i].time<temp.time){
                    temp = a[i];  ans = i;  }
            }
            System.out.println(ans>0?ans:"None");  }
    } static class num{ int number;  int time;  private num(int number,int time){ this.number = number;  this.time = time;  }
    }
}
发表于 2018-11-16 19:56:02 回复(0)
C/C++
Caffeine头像 Caffeine 
思路直接暴力求解
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct num
{
    int a;
    int count = 0;
    bool operator == (const int & i)
    {
        return this->a == i;
    }
};
int main(int argc, char *argv[])
{
    int n;

    while (cin >> n)
    {
        vector<struct num> v;
        int tmp;
        //memset(a, 0, sizeof(a));
        for (int i = 0; i < n; i++)
        {
            cin >> tmp;

            if (find(v.begin(), v.end(), tmp) != v.end())
            {
                vector<struct num>::iterator it = find(v.begin(), v.end(), tmp);
                it->count++;
            }
            else
            {
                struct num *p = new struct num;
                p->a = tmp;
                p->count++;
                v.push_back(*p);
            }
        }
        int firstCount = -1;
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i].count == 1)
            {
                firstCount = v[i].a;
                break;
            }
        }
        if (firstCount != -1)
        {
            cout << firstCount << endl;
        }
        else
        {
            cout << "None" << endl;
        }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

发表于 2018-08-25 19:00:43 回复(0)
potato520头像 potato520
//这个应该稍微更快点，没测试过。。。
#include "stdafx.h"
#include <cstdio>
int hashTable[10010] = {0};
int queue[10010] = {0};
int main(){
    int n, number;
    scanf("%d", &n);
    int cnt = 0;
    while(n--){
        scanf("%d", &number);
        hashTable[number]++;
        if(hashTable[number] == 1){
            queue[cnt++] = number;
        }
    }
    int i;
    for(i = 0; i < cnt; ++i)
        if(hashTable[queue[i]] == 1)break;
    if(i == cnt)printf("None\n");
    else printf("%d\n", queue[i]);
    return 0;
}
发表于 2018-07-28 09:50:50 回复(0)
袁博文202头像 袁博文202 
from collections import Counter
n = list(map(int, input().split()))[1:]
c = Counter(n)
ans = 0
for x in n:
    if c[x]==1:
        ans = x
        break
print(ans if ans else 'None')

发表于 2018-05-04 20:41:58 回复(0)
C/C++
OFShare头像 OFShare 
//map暴力。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,A[maxn];
map<int,int> mp;
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;++i)
        scanf("%d",&x),A[i]=x,++mp[x];    
    for(int i=1;i<=n;++i)
        if(mp[A[i]]==1)
            printf("%d\n",A[i]),exit(0);
    printf("None\n");
    return 0;
} 

发表于 2018-03-05 15:32:57 回复(0)
提交观点

问题信息

查找 排序
难度：
27条回答 11761浏览

热门推荐

通过挑战的用户

相关试题

Be Unique (20)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号