java - 我们如何修复这个算法来找到最小的数字

问题描述

我们想找到从给定长的数字创建的最小数字。

我们正在执行以下编程任务：https ://www.codewars.com/kata/573992c724fc289553000e95

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

#Task：根据语言返回一个数组或一个元组或一个字符串（参见“示例测试”）

1) the smallest number you got
2) the index i of the digit d you took, i as small as possible
3) the index j (as small as possible) where you insert this digit d to have the smallest number.

例子：

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

126235 是通过在索引 2 处取 1 并将其放在索引 0 处得到的最小数字

smallest(209917) --> [29917, 0, 1] or ...

[29917, 1, 0] could be a solution too but index `i` in [29917, 1, 0] is greater than 
index `i` in [29917, 0, 1].

29917 是通过在索引 0 处取 2 并将其放在索引 1 中得到的最小数字，它给出了 029917，即数字 29917。

smallest(1000000) --> [1, 0, 6] or ...

-> 我们写过：

public class ToSmallest {
    
    public static long[] smallest /**/ (long n) {
      System.out.println("\n\nn: "+n);
      StringBuilder input = new StringBuilder(String.valueOf(n));
      long min = Long.MAX_VALUE;
      int minIndex = -1;
      
      //We find the minimum and its index
      for(int i=input.length()-1; n>0; i--){
        long digit = n%10;
        if(min!=Math.min(min,digit)){
          minIndex='\0'+i;
        }
        min = Math.min(min, digit);
        n /= 10;
      }
      
      System.out.println("min: "+min);
      System.out.println("minIndex: "+minIndex);
      
      //We put the minimum as first digit
      input = input.deleteCharAt(minIndex);
      System.out.println("input: "+input);
      input = input.insert(0,min);
      System.out.println("input: "+input);
      
      return new long[]{Long.parseLong(input.toString()),minIndex,0};
    }
}

我们认为这是不完整的，因为我们假设在所有情况下我们都可以通过以下方式创建最小值：

1) Find the min digit
2) Remove it from where it was
3) Insert it at start

但是，作为单元测试：

import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;

public class ToSmallestTest {

    private static void testing(long n, String res) {
        assertEquals(res, 
                     Arrays.toString(ToSmallest.smallest(n)));
    }
    @Test
    public void test() {
        System.out.println("Basic Tests smallest");
        testing(261235, "[126235, 2, 0]");
        testing(209917, "[29917, 0, 1]");
        testing(285365, "[238565, 3, 1]");
        testing(269045, "[26945, 3, 0]");
        testing(296837, "[239687, 4, 1]");
    }
}

-> 代码在第二次测试中失败。

我们如何改进算法？

编辑：阅读 Norbert Dopjera 的回答后，我们尝试过：

public class ToSmallest {
    
    public static long[] smallest (long n) {
      System.out.println("\n\nn: "+n);
      StringBuilder input = new StringBuilder(String.valueOf(n));
      long min = Long.MAX_VALUE;
      int minIndex = -1;
      int numberMinsFound = -1; //
      
      //We find the minimum and its index
      
      while(numberMinsFound == minIndex){ //
        for(int i=input.length()-1; n>0; i--){
          long digit = n%10;
          if(min!=Math.min(min,digit)){
            minIndex='\0'+i;
          }
          min = Math.min(min, digit);
          n /= 10;
          numberMinsFound++; //
        }
      }
      
      System.out.println("min: "+min);
      System.out.println("minIndex: "+minIndex);
      
      //We put the minimum as first digit
      input = input.deleteCharAt(minIndex);
      System.out.println("input: "+input);
      input = input.insert(0,min);
      System.out.println("input: "+input);
      
      return new long[]{Long.parseLong(input.toString()),minIndex,0};
    }
}

然而，第二次测试仍然是错误的：

n: 209917
min: 0
minIndex: 1
input: 29917
input: 029917


expected:<[29917, [0, 1]]> but was:<[29917, [1, 0]]>

标签： javaalgorithm

java - 我们如何修复这个算法来找到最小的数字

问题描述

解决方案

推荐阅读