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

推荐订阅源

H
Help Net Security
博客园 - Franky
GbyAI
GbyAI
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
爱范儿
爱范儿
IT之家
IT之家
酷 壳 – CoolShell
酷 壳 – CoolShell
aimingoo的专栏
aimingoo的专栏
博客园_首页
MongoDB | Blog
MongoDB | Blog
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
Recent Announcements
Recent Announcements
Scott Helme
Scott Helme
有赞技术团队
有赞技术团队
M
MIT News - Artificial intelligence
C
CERT Recently Published Vulnerability Notes
K
KPMG report finds enterprise disconnect between AI and its ROI | CIO
Jina AI
Jina AI
F
Fortinet All Blogs
N
Netflix TechBlog - Medium
L
LangChain Blog
L
LINUX DO - 最新话题
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
H
Hacker News: Front Page
MyScale Blog
MyScale Blog
P
Palo Alto Networks Blog
G
Google Developers Blog
Google DeepMind News
Google DeepMind News
AI
AI
T
Troy Hunt's Blog
Microsoft Azure Blog
Microsoft Azure Blog
阮一峰的网络日志
阮一峰的网络日志
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
Vercel News
Vercel News
Microsoft Security Blog
Microsoft Security Blog
罗磊的独立博客
S
Secure Thoughts
大猫的无限游戏
大猫的无限游戏
博客园 - 叶小钗
人人都是产品经理
人人都是产品经理
Blog — PlanetScale
Blog — PlanetScale
博客园 - 司徒正美
Apple Machine Learning Research
Apple Machine Learning Research
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
博客园 - 三生石上(FineUI控件)
S
Security @ Cisco Blogs
Cloudbric
Cloudbric
E
Exploit-DB.com RSS Feed
Attack and Defense Labs
Attack and Defense Labs

博客园 - 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
也做了一下腾讯前端面试题
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倍。我用的是二进制位存储。