算法题:覆盖前缀 The first covering prefix of array ---哈希表

A non-empty zero-indexed array A consisting of N integers is given. The first covering prefix of array A is the smallest integer P such that 0≤P<N and such that every value that occurs in array A also occurs in sequence A[0], A[1], ..., A[P].

For example, the first covering prefix of the following 5−element array A:

A[0] = 2  A[1] = 2  A[2] = 1
A[3] = 0  A[4] = 1

is 3, because sequence [ A[0], A[1], A[2], A[3] ] equal to [2, 2, 1, 0], contains all values that occur in array A.

Write a function

class Solution { public int solution(int[] A); }

that, given a zero-indexed non-empty array A consisting of N integers, returns the first covering prefix of A.

Assume that:

N is an integer within the range [1..1,000,000];

each element of array A is an integer within the range [0..N−1].

For example, given array A such that

A[0] = 2  A[1] = 2  A[2] = 1
A[3] = 0  A[4] = 1

the function should return 3, as explained above.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

题目的大概意思：对一个数组A，比如A=[2,2,1,0,1],找出最小的p值，使A[0]~A[p]包含了A中所有的元素。A=[2,2,1,0,1]时，A中所有元素为2,1,0,显然A[0]~A[3]=[2,2,1,0]包含了所有的元素（2，1，0）

解决思路：题目要求是线性时间O(N),想到应该扫描整个数组，判断每个数字在它之前是否出现过，出现则为True，否则False，记对每个数字给出一个标记位，如果得到了这个数组，那么得到p的值就很简单了，从数组的最后一位往回扫描，第一个为False的位置即p的值

现在的问题是如何在线性时间判断一个值是否出现过，如果对每个值给标记位，值的可能性题目没说，很可能是int的范围，那数字太大，这个时候就应该联想到哈希表，哈希表就是在线性时间找到特定的key.

思路确定，代码就简单了，用python实现如下：

 1 def solution(A):
 2     hasht={}
 3     a=[]
 4     for ls in A:
 5         if hasht.has_key(ls):
 6             a.append(True)
 7         else:
 8             a.append(False)
 9             hasht[ls]=True
10     length=len(a)-1
11     while length>0:
12         if a[length]:
13             length-=1
14         else:
15             break
16     return length

用python自带的字典来实现哈希表的功能

BTW：最后得分100的感觉爽爆了