在12000毫秒内执行middlePermutation [英] execute middlePermutation in under 12000ms

问题描述

我正在执行 codewars 上的名为 Simple Fun#159:Middle Permutation 的任务.

I'm doing a task named Simple Fun #159: Middle Permutation on codewars.

说明是:

您将得到一个字符串s.s中的每个字母出现一次.

You are given a string s. Every letter in s appears once.

考虑通过重新排列s中的字母形成的所有字符串.后以字典顺序对这些字符串进行排序，返回中间术语.(如果序列的长度为偶数n，则将其中间项定义为(第n/2个词).

Consider all strings formed by rearranging the letters in s. After ordering these strings in dictionary order, return the middle term. (If the sequence has a even length n, define its middle term to be the (n/2)th term.)

这是我的代码:

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个测试时，我得到一个错误:

I succesfully passed all sample tests but when I try to pass 100 tests I get an error:

通过:5失败:0错误:1

Passed: 5 Failed: 0 Errors: 1

进程已终止.完成时间超过12000毫秒

Process was terminated. It took longer than 12000ms to complete

我的意思是我的代码实际上正在工作并解决问题，但是这花费了太多时间.如何在不到12000毫秒的时间内解决此问题?

I mean my code is actually working and solving the problem but it takes too much time. How can I solve this in less than 12000 ms?

推荐答案

让我们考虑一下4个字母.

Let's think about 4 letters.

a b c d

每个字母都有相等的份额成为第一.那是 4！/4 = 6 个排列.因此，第12个置换将以 ceil(12/6)= 2 为第二个字母

Each letter gets an equal share of being first. That's 4! / 4 = 6 permutations each. So the 12th permutation will start with ceil(12 / 6) = 2 that's the second letter

b

现在我们还剩下三个字母.左侧带有 b 的第一个排列是第七个.剩下的每个字母都相等地获得第二.那是 3！/3 = 2 个排列.因此，第12-6 =第6个排列(从第7个开始计数)将具有有序集合中的 ceil(6/2)= 3rd 字母，其中不包括 b :

Now we have three letters left. The first permutation with b on the left is the seventh one. Each letter that's left gets an equal share of being second. That's 3! / 3 = 2 permutations each. So the 12 - 6 = 6th permutation (counting from the 7th) will have the ceil(6 / 2) = 3rd letter from the ordered set that excludes b:

a c d
    ^

前往:

b d

现在我们还剩下两个字母.

Now we have two letters left.

a c

在左边的 b 之后是 d 的第一个排列(从第7个开始计数)是第五个.剩下的每个字母都等于第三(在这里检测模式吗?).那是 2！/2 = 1 排列.因此，从第7个开始的第5个开始的 12-6-4 = 2nd 排列:)将具有我们上一个集合中的 ceil(2/1)= 2nd 字母， {a，c} .

The first permutation (counting from the 7th) with d after b on the left is the fifth. Each letter that's left gets an equal share of being third (detect a pattern here?). That's 2! / 2 = 1 permutation each. So the 12 - 6 - 4 = 2nd permutation starting from the 5th after the 7th :) would have the ceil(2 / 1) = 2nd letter from our last set, {a, c}.

最终排列:

b d c a

现在，如果您能够理解并应用它，那么您已经赢得了！

Now if you can understand and apply that, you've earned it!

这篇关于在12000毫秒内执行middlePermutation的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！