我正在做一个名为Simple Fun #159: Middle Permutation的任务。
描述如下:
给你一个字符串s。s中的每个字母都出现一次。
考虑所有字符串,这些字符串是通过在s.after中重新排列字母而形成的。
按字典顺序排列这些字符串,返回中间项。
(如果序列具有偶数长度n,则将其中间项定义为
(n/2)第项。)
这是我的代码:

var alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur).join(''));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

function middlePermutation(s) {
  var variants = [],
      numbers = [],
      result = [],
      string = s.split('');
  variants = permutator(string);

  //convert to numbers
  for (var i = 0; i < variants.length; i++) {
    var current = variants[i].split('');
    for (var k = 0; k < current.length; k++) {
      current[k] = alphabet.indexOf(current[k]) + 1;
    }
    numbers.push(parseInt(current.join('')));
  }
  //get final array
  for (var i = 0; i < variants.length; i++) {
    result[i] = [];
    result[i].push(variants[i]);
    result[i].push(numbers[i]);
  }

  result.sort();

  if ((result.length % 2) !== 0) {
    return result[Math.ceil(result.length/2)][0];
  } else {
    return result[(result.length/2)-1][0];
  }
}

我成功地通过了所有的样本测试,但是当我试图通过100个测试时,我得到一个错误:
通过:5失败:0错误:1
进程已终止花了12000多毫秒才完成
我的意思是我的代码实际上是在工作和解决问题,但它需要太多的时间如何在12000毫秒内解决此问题?

最佳答案

让我们想想4个字母。

a b c d

每一个字母在第一名中所占的比例相等。这是每个排列所以第12个排列将以4! / 4 = 6开始,这是第二个字母
b

现在我们还剩三封信。左边ceil(12 / 6) = 2的第一个置换是第七个置换剩下的每一个字母都有同等的第二名这是每个排列。因此,12-6=6排列(从7开始计算)将具有排除b的有序集的3! / 3 = 2字母:
a c d
    ^

导致:
b d

现在我们还剩两封信。
a c

第一个排列(从第七个开始计算)在左边的ceil(6 / 2) = 3rd之后的b是第五个剩下的每一个字母在第三名中所占的比例相等(在这里检测到一个模式?)。这是每一个的排列。因此,从第5次到第7次开始的d排列:)将具有我们最后一组的b字母,2! / 2 = 1
最终排列:
b d c a

现在,如果你能理解并应用它,你就赢得了它!

09-19 07:26