會留里

stay hungry, stay foolish

超大整数列相加

昨天面试遇到了两道简单的算法题,对于算法盲的我来说当然 是扑街了。

1.m和n两个百万级长度级整数串相加怎么实现。

首先node.js的变量是存储不了这么长的int的,只能用str的形式存储,然后需要手动进行位数相加以及进位。

时间复杂度: O(m > n ? m : n)

代码:

// Node.js

'use strict';

let a = '', b = '';
for (let i = 0; i < 500000; i++) {
  a += parseInt(Math.random() * 100000);
}
for (let i = 0; i < 500000; i++) {
  b += parseInt(Math.random() * 100000);
}

var d = new Date();

let i = a.length-1;
let j = b.length-1;

let m = 0;
let s = '';

while (i >= 0 || j >= 0) {
  let _a = i >= 0 ? parseInt(a[i]) : 0;
  let _b = j >= 0 ? parseInt(b[j]) : 0;

  m = _a + _b + m;
  s = m % 10 + s
  m = m >= 10 ? 1 : 0;

  i--;
  j--;
}

console.log(s);
console.log(s.length);
console.log('time spend: ', new Date() - d);

2.长度为m的数组中查找最大的n个整数。

使用选择排序

时间复杂度: O(n*m)

代码:

// node.js

'use strict';

let d = new Date();

let arr = [];
for (let i = 0; i < 2000000; i++) {
  let r = parseInt(Math.random() * 10000);
  arr.push(r);
}

let m = arr.length;
let n = 10;

for (let i = 0; i < m; i++) {
  for (let j = i+1; j < m; j++) {
    if (arr[i] < arr[j]) {
      let k = arr[i];
      arr[i] = arr[j];
      arr[j] = k;
    }
  }
  if (i >= n-1) break;
}

console.log(arr.splice(0, n));
console.log('time spend: ', new Date() - d);