在12000毫秒内执行middlePermutation

本文介绍了在12000毫秒内执行middlePermutation的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在执行 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!