4

我正在尝试创建一个返回 int 的方法 - 发送数组中最大整数的值。我希望这种方法起作用的方式是在 for 循环中检查数组的第一个和最后一个元素，然后按它们的方式工作到中间。所以 i = 第一个整数，k = 最后一个整数。何时i = 0, k = n-1（索引），i = 1, k = n-2如果你赶上我的漂移。在每个循环中都需要检查if a[i]>a[k]. 然后他们交换位置。然后我知道最大的数字在数组的前半部分，然后我希望它检查那一半，所以最终最大的 int 在索引 0 处。

我试过这样：

public static int maxOfArray(int[] a)
{
    int length = a.length;

    if(length<1)
        throw new NoSuchElementException("Not at least one integer in array");

    while (length > 1)
    {
        int k = length;

        for(int i = 0; i < length/2; i++)
        {
            k--;

            if(a[i]<a[k])
            {
                int j = a[i];
                a[i] = a[k];
                a[k] = j;
            }
        }
        length /=2;
    }
    return a[0];
}

..但我真的不明白..我很难“想象”这里发生了什么..但它并不总是有效..（尽管有时）。

另编辑 ：数组 {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12}; 将吐出 17 作为最大的数字。我意识到我必须修复奇数长度的错误，但我想先解决这个偶数长度的数组..

4

9 回答 9

7

一个错误是遇到length奇怪的时候。

在这些情况下，您“错过”了中间元素。

示例：对于输入int[] arr = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };- 元素9将与自身进行比较和检查，但随后您减小 的大小，您从接下来要迭代的数组中length排除。9

我相信可以通过将问题减少到ceil(length/2)而不是length/2（并处理特殊情况length==1）来解决

评论中提到的另一个问题是：您需要迭代 up tolength/2而不是 up to length，否则您将覆盖自己。

最后 -标志是错误的。

if(a[i]>a[k])

应该

if(a[i]<a[k])

请记住 - 如果第一个元素较小，第二个元素较小，则您正在尝试交换元素，以便将较大的元素推到数组的头部。

于 2012-09-11T11:20:20.507 回答
3

但我真的不明白..我很难“想象”这里发生了什么..但它并不总是有效..（尽管有时）。

在这种情况下，您应该使用调试器单步执行代码，以了解每行代码的作用。

我会做的是：

public static int maxOfArray(int[] a) {
    int max = a[0];
    for (int i : a)
        if (max < i)
            max = i;
    return max;
}

public static int findMaxTheHardWay(int[] array) {
    for (int length = array.length; length > 1; length = (length + 1) / 2) {
        for (int i = 0; i < length / 2; i++) {
            if (array[i] < array[length - i - 1])
                array[i] = array[length - i - 1]; // don't need to swap.
        }
    }
    return array[0];
}

public static void main(String... args) {
    Random rand = new Random(1);
    for (int i = 1; i <= 1000; i++) {
        int[] a = new int[i];
        for (int j = 0; j < i; j++) a[j] = rand.nextInt();
        int max = maxOfArray(a);
        int max2 = findMaxTheHardWay(a);
        if (max != max2)
            throw new AssertionError(i + ": " + max + " != " + max2);
    }
}
于 2012-09-11T11:08:21.747 回答
3

这是解决问题的一种相当疯狂的方法，但我会一起玩。

问题出在内部循环中。

  • 你从 i = 0 和 k = 长度 - 1 开始。
  • 如果 a[i] > a[k] 你交换它们。
  • ...
  • 你最终得到 k = 0 和 i = length - 1
  • 如果 a[i] > a[k] 你交换它们。

如果你仔细看，你会注意到如果我们在第一次交换中交换了元素，我们也会在最后一次交换中交换它们；即我们将撤消第一次交换的影响。这同样适用于整个数组切片。

看？

您需要做的是中途停止内循环......然后考虑length奇怪的情况。

顺便说一句，我之所以称之为“相当疯狂”，是因为显而易见且简单的方法要快得多：O(N)与O(NlogN)

于 2012-09-11T11:29:33.057 回答
1 
int a[] = {1,7,3};   
List<Integer> list = Arrays.asList(a);  
Integer largest = Collections.max(list);

这将为您提供数组中的最大数字。

于 2012-09-11T11:23:32.173 回答
1

这是一个适合您想要的规格的解决方案（与这里的许多其他规格不同，嗯，嗯）：

    final Integer[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };

    int half = (input.length / 2);
    int mod = input.length % 2;
    while (half >= 0) {
        for (int i = 0, j = (half * 2) + mod - 1; i <= half && j >= half; i++, j--) {
            if (input[i] < input[j]) {
                final int tmp = input[i];
                input[i] = input[j];
                input[j] = tmp;
            }
        }
        if (half == 0) break;
        half = half / 2;
        mod = half % 2;
    }
    //Here, input[0] = the biggest number in the original input.

编辑：添加了 mod，所以如果最后一个元素是最大的，它就可以工作。

于 2012-09-11T11:25:46.123 回答
1

我认为您的代码正在运行，您只需要在奇数数组的情况下将长度 / 2 设置为上限，但我的测试返回正确的结果：

package org.devince.largestinteger;

import java.util.NoSuchElementException;

public class LargestInteger {
    final static int[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };
//  final static int[] input = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };
//  final static int[] input = {1,3,7};

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(String.valueOf(maxOfArray(input)));
    }

    public static int maxOfArray(int[] a)
    {
        int length = a.length;

        if(length<1)
            throw new NoSuchElementException("Not at least one integer in array");

        while (length > 1)
        {
            int k = length;

            for(int i = 0; i < length; i++)
            {
                k--;

                if(a[i]>a[k])
                {
                    int j = a[i];
                    a[i] = a[k];
                    a[k] = j;
                }
            }
            length = (int) Math.ceil(length / 2f);
        }
        return a[0];
    }

}
于 2012-09-11T11:57:02.860 回答
0

为什么不将数组的第一个值存储到变量max中。

之后，只需从第二个位置到最后一个位置循环遍历数组，在循环中只需检查当前值是否大于。max如果大于则分配max该值。

返回max，你有最大的数字。 

public int FindLargest()
{
    int[] num = { 1, 2, 5, 12, 13, 56, 16, 4 };
    int max = num[0];

    for (int i = 1; i <num.length; i++)
    {
        if (num[i] > max)
        {
            max = num[i];
        }
    }

    return max;
}
于 2012-09-11T11:12:41.493 回答
0

同样你也可以接近，

int length = a.length;
   while (length > 1)
    {
        int k = length;
        for(int i = 0; i < length; i++)
        { 
            for(int y = k-1; y >= i; y--) 
            {         
                if(a[i]<a[y])
                {
                    int j = a[i];
                    a[i] = a[y];
                    a[y] = j;               
                }
            }       
        }
        length /=2;
    }
于 2012-09-11T12:08:43.717 回答
0 
         final int validSampleRates[] = new int[]{
                    5644800, 2822400, 352800, 192000, 176400, 96000,
                    88200, 50400, 50000, 4800,47250, 44100, 44056, 37800, 32000, 22050, 16000, 11025, 4800, 8000};
          ArrayList <Integer> YourArray = new ArrayList <Integer> ():
 for (int smaple : validSampleRates){

                    YourArray.add(smaple);
                }
            Integer largest = Collections.max(YourArray);
            System.out.println("Largest   " + String.valueOf(largest));

最好的方法是使用将 List Collection 扩展为 ArrayList 的 Array

于 2016-11-17T17:03:33.710 回答