找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 795|回复: 0
收起左侧

[资源分享] 7: Prefix Array

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 01:10 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 uuuouou 于 10-3-2015 01:12 PM 编辑

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. };
复制代码

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表