objective-c - 如何最小化数组访问次数

Question

如何减少访问数组的时间，此时它访问数组 2 次以找到用户提供的数字序列中的最大数字，

int i=0;
    int max = -1;
    int a_i = -1;

    for (i=0; i<length; i++)
    {   
    a_i = array(a,i);

    if (a_i > max) 
    {
    max = a_i;
    }

    return max;

pastebin 上的完整代码

任何帮助表示赞赏。

Answer 1

• 简短的回答

你不能，你必须遍历每个项目，考虑到你没有关于数组的信息。

• 长答案

如果您接受之前浪费了一些时间，您可以减少阅读时的访问量

O(n)使用你需要插入（everyting）并O(n)找到最小值的数组

如果您真正想要的是减少在 find 函数中花费的时间，您可以使用minimum heap，插入时会有一些开销，O(n log(n))但您只需要O(1)搜索。

您也可以在搜索之前对数组进行排序，这可以是O(n log n)