找到最小的 - 密码 - 密码挑战-JavaScript

Question

试图解决该密码挑战。

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

任务：根据语言返回数组或元组或字符串(请参阅"示例测试"(，

1(您获得的最小数字

2(您拿到的数字D的索引i，我尽可能小

3(索引J(尽可能小(在其中插入此数字D的数字最小。

示例：

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));

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

编辑：最新尝试：

function smallest (n) {
  let array = Array.from(String(n)).map(Number);
  let original = Array.from(String(n)).map(Number);
  let sorted = Array.from(String(n)).map(Number).sort((a, b) => a - b);
  let swapValueOne = [];
  let swapValueTwo = [];
  for (let i = 0; i < array.length; i++) {
    if (array[i] !== sorted[i]) {
      swapValueOne.push(sorted[i]);
      swapValueTwo.push(original[i]);
      break;
    }
  }
  swapValueOne = Number(swapValueOne);
  swapValueTwo = Number(swapValueTwo);
  
  let indexOne = original.indexOf(swapValueOne);
  let indexTwo = original.indexOf(swapValueTwo);
  //remove swapValue
  array.splice(indexOne, 1);
  //insert swapValue
  array.splice(indexTwo, 0, swapValueOne);
  return ([Number(array.join("")), indexOne, array.indexOf(swapValueOne)]);
}
console.log(smallest(296837));

^有时会给正确的数字带有正确的交换索引，有时数字和掉期指数都是错误的。

Answer 1

将最小元素放在前面(我们称其为"贪婪"解决方案(是非最佳选择的。考虑到n = 296837的情况，例如您上次测试案例。您的代码返回[296837, 0, 0]，因为它发现2是最小的数字，并且它将其移至前面(本质上什么也不做(。如您的示例所示，有一个更好的方法：[239687, 4, 1]，也就是说，将3移至数组中的第一个索引。

您需要将策略重新制定为非纠正以找到全球最佳。

如果您仍然卡住，可以尝试以下操作：

数字不能包含很多数字 - 为什么不尝试所有可能的交换？

Answer 2

这是一个可能会有所帮助的小主意。

如果您有类似的数字：

239687

您可以用这数数字来制作的最小数字：

236789

在原始数字中，2和3在正确的位置。如果您从数字的左侧和排序数字开始，则发现的第一个区别是需要交换的数字。它需要在排序列表中与相应的数字交换：

orig   2 3 9 6 8 7 -- 6 needs to go before 9
       | | x       
sorted 2 3 6 7 8 9

下一个排序的数字上方是6，但原件有9。您需要在9。

之前插入6。

对于算法，您可以对数字进行分类并找到第一个差异的索引(从左开始(。这是您的返回值之一(在示例中为2(。现在在原始(索引3(中找到sorted[2](即6(的索引。在原始数组中插入值，然后完成。

Answer 3

查找第一个未排序元素的方法未正确求解所有情况，例如，如果数字为300200，则第一个未排序的数字是3，如果您将0放在该数字中位置，取决于您移动的0：

(0(30020(0(30020(0(30200(0(30200

所有答案都是错误的，因为您要做的就是将3个数字放在数字末尾以获取

(000(2003