小编use*_*907的帖子

作为输入,浮标的排序后的数组,我需要找到对的总数(i,j)如A[i]*A[j]>=A[i]+A[j]对于每个i < j.我已经知道了天真的解决方案,在其他循环中使用循环,这将给我O(n ^ 2)算法,但我想知道是否有更优化的解决方案.

我已经开始玩鳕鱼并遇到了这个问题:

给出了由N个不同整数组成的零索引数组A. 该数组包含[1 ..(N + 1)]范围内的整数,这意味着只缺少一个元素.

你的目标是找到缺少的元素.

写一个函数:

int solution(int A[], int N); 

Run Code Online (Sandbox Code Playgroud)

在给定零索引数组A的情况下,返回缺少元素的值.

例如,给定数组A,使得:

A [0] = 2 A [1] = 3 A [2] = 1 A [3] = 5

函数应该返回4,因为它是缺少的元素.

假使,假设:

    N is an integer within the range [0..100,000];
    the elements of A are all distinct;
    each element of array A is an integer within the range [1..(N + 1)].

Run Code Online (Sandbox Code Playgroud)

复杂:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting …

Run Code Online (Sandbox Code Playgroud)