LeetCode题解如何对 1 千万个整数进行快速排序

输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出:按升序排列的输入整数的列表。

约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化。

题解:``` .js
/**
* Array存储一个数字耗费一个字节,一个字节又对应8个bit,每个bit可以表示一个数,0表示没有此数,1表示有此数
* 比如:1,2,3,10,在Array中的存储为
* [7,2]
* 7的二进制为 00000111 后面三个1分别表示1,2,3
* 2的二进制位 00000010
*
* 这样array的每位可以用来表示8个数,那么一千万个数的话,就只需要1250000byte表示,
* 1250000/1024/1024 约等于 1M
*
* @param {*} inputFile
*/
function sortBigArrays(inputFile) {
var array = new Array(1).fill(0);
var number = '';

var readerStream = fs.createReadStream(inputFile, {
highWaterMark: 1
});

readerStream.on('data', function (chunk) {
if (chunk == ',') {
putNumberIntoMap(array, +number);
number = '';
} else {
number += chunk;
}
});

readerStream.on('end', function () {
putNumberIntoMap(array, +number);
var wtStream = fs.createWriteStream('output.txt');
for (var i = 0, len = array.length; i < len; i++) {
// console.log('output ', i, ' into file');
if (array[i] && array[i] != 0) {
// 输出到文件
var base = 8 * i;
var t = array[i].toString(2).split('').reverse();
for (var j = 0; j < t.length; j++) {
if (t[j] == '1') {
wtStream.write((base + j + 1) + (i == len - 1 ? '' : ','));
}
}
}
}
wtStream.end();
});

function putNumberIntoMap(array, number) {
var posIndex = number % 8;
var arrayIndex = parseInt(number / 8);
posIndex = posIndex == 0 ? (arrayIndex--, 7) : posIndex - 1;

var sum = array[arrayIndex] == null ? array[arrayIndex] = 0 : array[arrayIndex];
sum = sum.toString(2).split('');

while (sum.length != 8) {
sum.unshift('0');
}
sum[7 - posIndex] = '1';
array[arrayIndex] = parseInt(sum.join(''), 2);
}
}
```

45码

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候,一个真实的面试题,这是一个开放题。题目描述:想办法,将一个城市的所有灯泡数量统计出来。题解:费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里,每套房有灯泡5只,那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡,那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的,具体应…

LeetCode题解黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可

LeetCode题解圆上任取三点构成锐角三角形的概率

来自字节跳动的一道几何题题解:1/4

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。