惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Jina AI
Jina AI
博客园 - Franky
Apple Machine Learning Research
Apple Machine Learning Research
酷 壳 – CoolShell
酷 壳 – CoolShell
阮一峰的网络日志
阮一峰的网络日志
量子位
雷峰网
雷峰网
宝玉的分享
宝玉的分享
V
Visual Studio Blog
博客园_首页
小众软件
小众软件
The Cloudflare Blog
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
大猫的无限游戏
大猫的无限游戏
博客园 - 聂微东
S
SegmentFault 最新的问题
博客园 - 【当耐特】
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
博客园 - 叶小钗
月光博客
月光博客
博客园 - 三生石上(FineUI控件)
人人都是产品经理
人人都是产品经理
WordPress大学
WordPress大学

博客园 - NeilChen

恢复 Windows 7 的“回到父目录”按钮 FireFox 脑残的安全设定 SQL Server 事务自动回滚 下载 infoq 网站视频 Select prototyping tools Lisp in Small Parts TechTalk by Peter Seibel on Common Lisp 时隔3年,再做双倍超立方数的题目,这次用Lisp Racket, SICP stream learning Operation is not valid due to the current state of the object lisp 笔记 - 闭包 Common Lisp 在 Windows 上的开发环境比较 翻译英文技术文章是一件很可耻的事情吗? 写了个博客备份的 ruby 程序 体验 Clozure CL 试用 Portable Allegro Serve Windows XP, Emacs, CLisp, SLIME 关于 Business Rule Engine Irony - 一个 .NET 语言实现工具包
也做了一下腾讯前端面试题
NeilChen · 2012-07-02 · via 博客园 - NeilChen

看到这个帖子:http://www.cnblogs.com/ilian/archive/2012/07/01/tx-test-entry.html

当时就想到了《编程珠玑》里讲到的 bitmap 算法。在 EditPlus 里敲了一下,实现如下:

 <script>

// Array Remove - By John Resig (MIT Licensed)
Array.prototype.remove = function(from, to) {
  var rest = this.slice((to || from) + 1 || this.length);
  this.length = from < 0 ? this.length + from : from;
  return this.push.apply(this, rest);
};

var arr = [];
for (var i = 0; i < 100000; i++)
    arr[i] = i;

arr.remove(73501);
arr.remove(17);
arr.remove(2);

var t1 = new Date();

var bitmap = [];
//for (var i = 0; i < 12500; i++)
//
    bitmap[i] = 0;

for (var i = 0; i < arr.length; i++){
    var x = arr[i];
    var j = Math.floor(x / 8);
    bitmap[j] = bitmap[j] | (0x80 >> (x % 8));
}

for (var x = 0; x < bitmap.length; x++){
    var b = bitmap[x];
    if (b == 255) continue;

    for (var i = 0; i < 8; i++) {
        if (((0x80 >> i) & b) == 0)
            document.write("Found missing number: " + (x * 8 + i) + "<br/>");
    }
}

var t2 = new Date();

document.write(t2 - t1);

</script>

原帖子里几个答案用到的类似方法貌似是直接分配的和原数组一样大的数组作为位图来查找,貌似比我这个空间上要浪费多7倍。我用的是二进制位存储。