找到最小的 - 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