java 查找数组中最大整数的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12368240/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to find the largest integer in array
提问by Sti
I am trying to create a method which returns an int - the value of the largest integer in the sent array.
The way I want this method to work, is to check the first andthe last element of the array in a for-loop, and work their way to the middle. So i = first integer, k = last integer. When i = 0, k = n-1(indexes), when i = 1, k = n-2if you catch my drift. In every loop it needs to check if a[i]>a[k]. Then they switch places. Then I know that the largest number is in the leading half of the array, and then I want it to check that half, so ultimately the largest int is at index 0.
我正在尝试创建一个返回 int 的方法 - 发送数组中最大整数的值。我希望此方法工作的方式是在 for 循环中检查数组的第一个和最后一个元素，然后从中间移到中间。所以 i = 第一个整数，k = 最后一个整数。当i = 0, k = n-1（索引），当i = 1, k = n-2你抓住我的漂移。在每个循环中，它都需要检查if a[i]>a[k]. 然后他们互换位置。然后我知道最大的数字在数组的前半部分，然后我希望它检查那一半，所以最终最大的 int 位于索引 0 处。
I tried like this:
我试过这样：
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];
}
..but I don't really get it.. I'm having a hard time "picturing" what's happening here.. But it's not always working.. (though sometimes).
..但我真的不明白..我很难“想象”这里发生的事情..但它并不总是有效..（尽管有时）。
EDITAlso: The array {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12}; will spit out 17 as the largest number. I realize I have to fix the odd-length bug, but I would like to solve this even-length array first..
编辑另外：数组 {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12}; 将吐出 17 作为最大的数字。我意识到我必须修复奇数长度的错误，但我想先解决这个偶数长度的数组。
回答by amit
A bug is when encountering lengthis odd.
一个错误是遇到length奇怪的时候。
In these cases, you "miss" the middle element.
在这些情况下，您“错过”了中间元素。
Example: for input int[] arr = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };- the element 9will be compared and checked against itself, but then you reduce the size of length, you exclude 9from the array you are going to iterate next.
示例：对于输入int[] arr = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };- 元素9将与其自身进行比较和检查，但随后您减小了 的大小length，您将其9从接下来要迭代的数组中排除。
I believe it can be solved by reducing the problem to ceil(length/2)instead of length/2(and handling special case of length==1)
我相信可以通过将问题减少到ceil(length/2)而不是length/2（并处理 的特殊情况length==1）来解决
The other issue as was mentioned in comments is: you need to iterate up to length/2rather then up to length, otherwise you are overriding yourself.
评论中提到的另一个问题是：您需要迭代到length/2而不是到length，否则您将覆盖自己。
Lastly - the sign is wrong.
最后 -标志是错误的。
if(a[i]>a[k])
should be
应该
if(a[i]<a[k])
Remember - you are trying to swap the elements if the first is smaller the the second in order to push the larger elements to the head of your array.
请记住 - 如果第一个元素小于第二个元素，您将尝试交换元素，以便将较大的元素推送到数组的头部。
回答by Peter Lawrey
but I don't really get it.. I'm having a hard time "picturing" what's happening here.. But it's not always working.. (though sometimes).
但我真的不明白..我很难“想象”这里发生的事情..但它并不总是有效..（尽管有时）。
In that case you should use a debugger to step through the code to get a picture of what each line of code does.
在这种情况下，您应该使用调试器逐步执行代码以了解每行代码的作用。
What I would do is:
我会做的是：
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);
}
}
回答by Stephen C
This is rather a crazy way to solve the problem, but I'll play along.
这是解决问题的相当疯狂的方法，但我会一起玩。
The problem is in the inner loop.
问题出在内部循环中。
- You start out with i = 0 and k = length - 1.
- If a[i] > a[k] you swap them.
- ...
- You end up with k = 0 and i = length - 1
- If a[i] > a[k] you swap them.
- 你从 i = 0 和 k = length - 1 开始。
- 如果 a[i] > a[k] 你交换它们。
- ...
- 你最终得到 k = 0 和 i = length - 1
- 如果 a[i] > a[k] 你交换它们。
If you look at that carefully you will notice that if we swapped the elements in the first swap, we will also swap them in the last swap; i.e. we will UNDO the effects of the first swap. And the same applies pair-wise through the entire array slice.
如果你仔细观察，你会注意到如果我们在第一次交换中交换了元素，我们也会在最后一次交换中交换它们；即我们将撤销第一次交换的影响。这同样适用于整个数组切片成对。
See?
看？
What you need to do is to stop the inner loop half way ... and then take account of the case where lengthis odd.
您需要做的是中途停止内部循环......然后考虑length奇数的情况。
By the way, the reason I called this "rather crazy", because the obvious and simple way is much faster: O(N)versus O(NlogN)
顺便说一句，我之所以称之为“相当疯狂”，是因为明显而简单的方法要快得多：O(N)vsO(NlogN)
回答by Vince
I think your code is working, you just have to ceil the length / 2 in case of odd array but my tests return proper result:
我认为您的代码正在运行，您只需要在奇数数组的情况下限制长度 / 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];
}
}
回答by Azuu
int a[] = {1,7,3};
List<Integer> list = Arrays.asList(a);
Integer largest = Collections.max(list);
This will give you Largest number in Array.
这将为您提供数组中的最大数字。
回答by Tobb
Here is a solution that fits the specifications that you want (unlike many other here, humm, humm):
这是一个符合您想要的规格的解决方案（与这里的许多其他解决方案不同，嗯，嗯）：
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.
Edit: Added mod, so it works if the last element is the largest..
编辑：添加了 mod，所以如果最后一个元素是最大的，它就可以工作。
回答by Priyank Patel
Why not just store the first value of the array to a variable max.
为什么不将数组的第一个值存储到变量中max。
After that just loop through the array starting from second position till the last ,
in the loop just check if the current value is greater than maxor not.If it is greater just assign maxthat value.
之后，从第二个位置开始循环遍历数组，直到最后一个，在循环中只检查当前值是否大于max或不大于max。如果大于则分配该值。
Return maxand you have the largest number.
返回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;
}
回答by Sivaraman
As the same u can approach like also,
同样，你也可以接近，
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;
}
回答by Fatih ?ennik
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));
The best way is to use Array that extends List Collection as ArrayList
最好的方法是使用将 List Collection 扩展为 ArrayList 的 Array
