找到最小的 - Codewars 挑战 - Javascript

Question

试图解决这个Codewars 挑战。

您有一个由数字组成的正数 n。您最多可以执行一个操作：选择数字中某个数字的索引，在该索引处删除该数字并将其插入到另一个或数字中的同一位置，以便找到您可以获得的最小数字。

任务：根据语言返回数组或元组或字符串（请参阅“示例测试”）：

1）你得到的最小数字

2）你取的数字d的索引i，i越小越好

3) 插入这个数字 d 以获得最小数字的索引 j（尽可能小）。

例子：

smallest(261235) --> [126235, 2, 0] or (126235, 2, 0) or "126235, 2, 0"

其他例子：

209917, [29917, 0, 1]

285365, [238565, 3, 1]

269045, [26945, 3, 0]

296837, [239687, 4, 1]

因此，为了获得尽可能小的数字，我们需要从数字中删除最小的数字并将其放在数字的前面，对吗？

function smallest (n) {

  //turn n into an array

  let array = String(n).split("").map(Number);

  

  let smallest = Math.min(...array);

  

  //find index of smallest in original array

  let index = array.indexOf(smallest);

  

  //remove smallest from original array, move it to front

  array.splice(index, 1);

  array.unshift(smallest);

  let newNumber = Number(array.join(""));

  //return array of new number, index of where the smallest was, 

  //and index of where the smallest is now

  return ([newNumber, index, 0]);

}

console.log(smallest(239687));

我的答案是返回正确的数字，但是，大约有一半的时间，它没有返回正确的 indexi和 index j。

Answer 1

将最小的元素放在前面（我们称之为“贪婪”解决方案）不是最优的。考虑一下 where 的情况n = 296837，就像上一个测试用例一样。您的代码返回，[296837, 0, 0]因为它发现它2是最小的数字并将其移到前面（本质上什么都不做）。正如您的示例所示，有一种更好的方法：[239687, 4, 1]，即移动3到数组中的第一个索引。您需要重新制定策略以不贪婪地找到全局最优解。如果您仍然卡住，您可以尝试以下操作：数字不能包含那么多数字——为什么不尝试所有可能的交换？

Answer 2

找到第一个未排序元素的方法不能正确解决所有情况，例如如果数字是 300200，第一个未排序的数字是 3，如果你在那个地方放一个 0，取决于你移动的 0 你得到了什么：(0)30020 (0)30020 (0)30200 (0)30200所有的答案都是错误的，因为你要做的就是把 3 放在数字的末尾才能得到(000)2003