java 通过优先级队列和程序中断获得数组中的最大数?

wvyml7n5  于 2023-03-06  发布在  Java
关注(0)|答案(1)|浏览(76)

前几天,一位招聘人员问了我一个问题:
当被要求找出数组中的最大数时,你会使用排序还是for循环(保持在非常大的数组上执行优先级的时间效率),程序应该在找到最大的元素后结束,所以不需要对数组或之后的元素做任何事情。
我对这些类型的编码难题(例如,询问非常大的数组的优先级)是新手,所以我的第一关是:

public class Solution {
    public static int getLargestNumber(int[] array) {
        Arrays.sort(array);
        return array[array.length-1];
    }
}

单元测试:

@Test
public void largestNumber() {
    int [] array = new int [] {17, 21, 3, 6, 9, 3, 15};
    int largestNumber = Solution.getLargestNumber(array);
    assertEquals(21, largestNumber);
}

然而,基于这个问题,这是在寻找类似于优先级队列的其他东西吗?一旦获得最大数量,就结束意味着什么?

t9aqgxwy

t9aqgxwy1#

你似乎想多了--你可以只对数组执行一次简单的for循环,存储max值,然后在末尾返回它:

public int getLargest(int[] arr)
{
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < arr.length; i++)
  {
    max = arr[i] > max ? arr[i] : max;
  }
  return max;
}

如果我是在面试中这样做的,我可能还会问一些边缘情况,比如“如果数组为空会怎么样”或者“我们是否需要将其扩展到其他类似的数据类型,比如字符串”,但就问题的范围而言,这样的问题是可以的。
Sorting和PriorityQueues对于这种简单的算法来说都不是理想的,因为它们都需要O(nlog(n))的时间,也可能需要O(n)的空间,一个简单的循环需要O(n)的时间和O(1)的空间,这要好得多。
现在,如果你想找到K个最大的数,那么排序或PQ会非常合适。

相关问题