代码之家 › 专栏 › 技术社区 › Behl

需要更有效的方法读取子数组

time-limiting coding-efficiency loops algorithm arrays

0

Behl · 技术社区 · 6 年前

我所做的:

我从I=0到n-2运行了一个循环:
限制条件:
1<=n<=10^5
1<=ai<=10^9

for(int i=0;i<n-2;i++)
{
    int r=i+2;
    vector<int> temp(inp.begin()+i,inp.begin()+r+1);
    sort(temp.begin(),temp.end());
    max_elem=temp[1];min_elem=temp[0];
    int maximum=temp[temp.size()-1];


    //cout<<max_elem<<" "<<min_elem<<"\n";

    while(r<n && max_elem+min_elem >= maximum)
    {   
        //cout<<max_elem<<" "<<min_elem<<" "<<inp[r]<<"\n";
        cnt++;
        r++;

        if(inp[r]<min_elem) {max_elem=min_elem;min_elem=inp[r];}
        else if(inp[r]<max_elem) max_elem=inp[r];
        else if(inp[r]>maximum) maximum=inp[r];

    }

}
cout<<cnt<<"\n";

一1 :
5个

O1号
6个
说明:
次阵列

二 :

氧气

说明:
(1,2,3),(2,3,5),(3,5,6)--(注:1,2,3,5不是ans coz 1+2<5)

2 回复 | 直到 6 年前

1

0

Emut 6 年前

一个天真的做法是这样做,这是如下。你的逻辑是正确的,这就是我实现的。我改变了排序(NlogN),只找到了最小和最大的两个数字。我没有编译代码,也不确定它是否按预期工作。它具有(n*n*n)的总体复杂性。

执行时间可以通过执行一些额外的检查来提高:

min1 + min2 >= max 条件可以在每个内部(k)循环之后检查,如果违反单个情况,则中断。

int min1;
int min2;
int max;
int count = 0;
for(int i = 2; i < n; i++){
    for(int j = 0; j < i - 2; j++){
        max = -1;
        min1 = min2 = 1000000000;
        for(int k = j; k <= i; k++){
            if(inp[k] > max)
                max = inp[k];
            if(inp[k] < min1){
                min1 = inp[k];
                continue;
            }
            if(inp[k] < min2){
                min2 = inp[k];
            }
        }
        if(min1 + min2 >= max)
            count++;
    }
}

2

0

juvian 6 年前

可能有一些bug,但这里是O(n logn)解决方案的一般思想:

我们有一个从startIdx到endIdx的元素窗口。如果它是一个有效的子数组,这意味着我们可以扩展它,我们可以添加另一个元素到它,所以我们增加endIdx。如果它是无效的,那么无论我们如何扩展它都是无效的,所以我们需要通过增加startIdx来减少它。

伪码:

multiset<int> nums;

int startIdx = 0, endIdx = 0;
int sol = 0;

while(endIdx != inp.size()) {
    if (endIdx - startIdx < 3) {
       nums.add(inp[endIdx]);  
       endIdx++;
    } else  {
       if (nums.lowestElement() + nums.secondLowestElement() < nums.highestElement()) {
          nums.remove(nums.find(inp[startIdx]));
          startIdx++;
       } else { 
            sol += endIdx - startIdx - 2; // amount of valid subarrays ending in inp[endIdx - 1]
            nums.add(inp[endIdx]);  
            endIdx++;
       }
    }
}