我有两个数组,一个非常大(超过一百万个条目),另一个数组很小(少于 1000 个条目),找到数组中所有条目的最大数量的最佳方法是什么?
谢谢。
如果数组未排序,则必须进行线性搜索以找到每个数组中的最大值。如果数组已排序,则只需从每个数组中取出第一个或最后一个元素(取决于排序顺序)。
如果你想一想,如果你想找到最高的值,你必须检查所有的值。没有办法解决这个问题(除非对数组进行排序,这很容易 - 只需取每个数组的最后一个值(如果按降序排序,则取第一个值)并取最大的值)。示例:
int highest = array1[0]; // note: don't do this if the array could be empty
for(int i = 1; i < array1.length; i++) {
if(highest<array1[i]) highest = array1[i];
}
for(int i = 0; i < array2.length; i++) {
if(highest<array2[i]) highest = array2[i];
}
// highest is now the highest
如果你的数组已经排序,你可以跳到最大值的末尾。
如果您的数组未排序,您将必须遍历整个列表,跟踪迄今为止看到的最大值。
这里我给出了从 int 数组中查找最大值的简单代码。 我的逻辑是:- 数组是 int[] arr={8,5,6,7,3,4,9} 。首先取一个临时变量并放入第一个 该变量中的值并假设这是最大值,即 tempValue=arr[0]。在 for 循环内部采用 if 块并检查第二个值是否大于第一个值。类似地,if 块将自动检查其余值。最后将最大值分配给临时变量并得到结果给定数组中的最大值为 9。
public class MaxIntArray{
public static void main(String[] args){
int[] arr={8,5,6,7,3,4,9};
int tempValue=arr[0];
for(int i=0;i<arr.length;i++){
if(arr[i]>tempValue){
tempValue=arr[i];
}
}
System.out.println("\n Maximum Value in the Given Array = "+tempValue);
}
}
输出是:
Maximum Value in the Given Array = 9
对于未排序的数组,您可以将最大数字变量初始化为 0(假设数组由正值组成),然后迭代数组中的所有项目,在每次迭代时将较大的数字分配给最大变量。
int[] values = {8,3,7,10,5};
max = 0;
for(int i = 0;i < values.length;i++){
if(values[i] > max){
max = values[i];
}
}
System.out.println(max);
此示例使用 Swift。
let max: UInt8 = [1,4,3].compactMap { $0 }.reduce(UInt8(0)) { $0 > $1 ? $0 : $1 } // 4
这个解决方案是当你有一个对象数组,并且你希望从中找到属性的最大值时。
这里,我们有一系列工作(有各自的利润和截止日期),我们需要找到最赚钱的工作。
class Job
{
int deadline; int profit;
public Job(int deadline, int profit)
{
this.profit = profit;
this.deadline = deadline;
}
public int getDeadline()
{
return deadline;
}
public int getProfit()
{
return profit;
}
public String toString()
{
return "Job [deadline:"+this.deadline+" profit:"+this.profit+"]";
}
}
找到最赚钱工作的方法。
static int jobSequenceWithMaxProfit(Job[] jobsAndProfits)
{
List<Job> lst= Arrays.asList(jobsAndProfits);
int maxProfit= Collections.max(lst, (Job a1, Job a2)->{ return a1.getProfit()- a2.getProfit();}).getProfit();
return maxProfit;
}
我们可以将您的操作或比较次数减少到 3(n/2-2)。从 2n(n 用于使用线性搜索查找最大数,n 用于查找最小值)。假设我们有一个元素数组 [1,9,8,7,4,5,1,4,7,8,1,6]。 将第一个元素设置为 Max=1,下一个元素设置为 Min=9,现在同时取数组的下两个元素进行比较,然后与 Max 和 Min 进行比较。因此一次迭代只需要 3 次比较,但数组减少到 n/2。因此,比较的总数将为 3(n/2-2)。 示例:
Max=arr[1];
Min=arr[2];
for(int i=3; i< arr.length;i=i+2)
{
if(arr[i]>arr[i+1])
{
if(Max < arr[i])
Max=arr[i];
if(Min > arr[i+1])
Min=arr[i+1];
}
else
{
if(Max < arr[i+1])
Max=arr[i+1];
if(Min > arr[i])
Min=arr[i];
}
}