7: Prefix Array

uuuouou

hash+linear scan，测试表明用数组模拟hash比每次unordered_set快3倍左右

1. class Solution {
   
2.         static const int MAX_N = 1000000;
   
3.         char in[MAX_N];
   
4. public:
   
5.         int leastPrefix(vector<int> &A) {
   
6.                 for(int x : A) in[x] = 0;
   
7.                 int n = A.size(), k = 0;
   
8.                 for(int i = 0; i < n; ++i){
   
9.                         if(!in[A【i】]){
   
10.                                 in[A【i】] = 1;
    
11.                                 k = i;
    
12.                         }
    
13.                 }
    
14.                 return k;
    
15.         }
    
16. };

复制代码