首页 > 试题广场 >

Be Unique (20)

[编程题]Be Unique (20)

热度指数：2948 时间限制：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, 10⁴ ]. 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 (<=10⁵) 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

输出

算法知识视频讲解

推荐

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)