0

该程序的目标是使数组中的所有数字都相同。您必须每次递增数组中的所有值，除了一个。然后程序将打印出使所有数字相同所需的最少步数。我有一个我认为是可行的解决方案，我只是想让它更有效率，有人有什么想法吗？在下面的代码中，用户将数字的初始值输入到数组中，然后计算所需的步数

public static void main(String[] args) throws NumberFormatException, IOException 
{
counter=0;
         size=sc.nextInt();
         input= new int[size];
        for(int k=0; k<size; k++)
        {
            input[k]=sc.nextInt();
        }
        while(!isAllEqual(input))
        {
            Arrays.sort(input);
            for(int k=0; k<input.length-1; k++)
            {
                input[k]++;
            }
            counter++;
        }
        pw.println(counter);

public static boolean isAllEqual(int[] a){
    for(int i=1; i<a.length; i++){
        if(a[0] != a[i]){
            return false;
        }
    }
return true;
}
4

2 回答 2

6

如果您将步骤更改为更简单的内容，可能会更容易理解这一点。如果我们只讨论值之间的相等性（即相对值，而不是绝对值），那么一次增加和减少所有值没有区别。如果我们将步骤更改为“除一之外的所有值都递增，然后将每个值减一”，我们可以看到除一之外的所有值都递增等于递减单个值。

如果步长是“减一值”，你能算出使值相等的步数吗？它应该涉及在最大处循环数组两次，并且不进行排序。

于 2013-01-01T22:55:42.820 回答
3

重大编辑，因为我误读了这个问题

只需扫描一次列表即可找到列表中的最小值以及所有值相加的总和。

获得这两个值后，所需增量的数量为：

[所有值的总和] - [列表中的项目数] * [最小值]

在代码中：

public static int numberOfSteps(int[] a) {
    if( a.length==0 ) return 0;

    int min= a[0];
    int total = a[0];
    for(int i=1;i<a.length;i++) {
        if( a[i] < min ) min = a[i];
        total += a[i];
    }

    return total - a.length * min;
}

这是因为（正如 Matti Virkkunen 指出的那样）每个项目的递减次数对于(a[i] - min )整个列表来说都是如此sum(a[i]-min)，我们可以将其扩展到sum(a[i]-(length*min).

相应的增量将在每一步增加所有内容，除了最右边的项目，它等于最大值。例如：

初始状态 = (0,1,1,1) 1. 增加除 a[3] 之外的所有内容 --> (1,2,2,1) 2. 增加除 a[2] 之外的所有内容 --> (2,3, 2,2) 3. 增加除 a[1] --> (3,3,3,3) 之外的所有内容：三步解决方案 = (1+1+1) - (4 * 0)

再次，（1,2,3,3）的初始状态

  1. 递增除 a[3] 之外的所有内容 --> (2,3,4,3)
  2. 递增除 a[2] 之外的所有内容 --> (3,4,4,4)
  3. 递增除 a[3] 之外的所有内容 --> (4,5,5,4)
  4. 递增除 a[2] 之外的所有内容 --> (5,6,5,5)
  5. 递增除 a[1] --> (6,6,6,6) 之外的所有内容：五步解决方案 = (1+2+3+3) - (4 * 1)
于 2013-01-01T22:57:59.520 回答