MENU

枚举+优化(5)——双指针优化1

June 9, 2018 • Read: 156 • 算法

有时候我们要对一个数组进行i和j两个下标的双重循环枚举

for(int i = 0;i < n;i++)
{
    for(int j = i + 1;j < n;j++)
    {
        ...
    }
}

image
从上面的代码我们能看出时间复杂度是O(N^2^)

双指针优化

在某些情况下,根据题目要求,j下标并不需要从i+1重新往后枚举一遍,而是跟随着i向后移动,j也向后移动

image
当红色i下标向右移动时,绿色下标不会向左移动。它有可能不动,也有可能向右,但是不会向左。由于j坐标不会向左移动,所以整个枚举的复杂度是O(N)

例1

给定N个整数A1,A2,...,AN,以及一个正整数k。问在所有的大于等于k的两个数的差(Ai-Aj)中,最小的差是多少?(N<=100000)

思路

首先对A数组排序,比如假设排好序的A数组是:A=[1,3,7,8,10,15],k=3,这时我们枚举两个数中较小的是A[i],较大的是A[j];对A[i]来说,我们要找到最优的A[j],也就是最小的A[j]满足A[j] - A[i] >= k

image
从上面的图我们可以看出:当A[i]=1时,最优的A[j]=7;当A[i]=3时,最优的A[j]=8;当A[i]=7时,最优的A[j]=10,这个“最优的A[j]”要么不动要么向右,不会向左。换句话说,我现在已知A[i]=1的时候,A[j]=7是最优的解;那么当A[i]变成3的时候,A[j]就可以从7的位置向后找,不用向前找。

#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n,k,ans,a[10000];
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    sort(a,a + n);
    if(a[n - 1] - a[0] < k){
        cout << "no solution" << endl;
        return 0;
    }
    ans = a[n - 1] - a[0];
    for(int i = 0,j = 0;i < n;i++)//枚举A[i]
    {
        while(j < n && a[j] - a[i] < k)
            j++;
        if(a[j] - a[i] >= k && a[j] - a[i] < ans)
            ans = a[j] - a[i];
    }
    cout << ans;
    return 0;
} 

例2 题目链接:hihoCoder1745

image

思路1:暴力枚举

假设A1~AN的最大值是P,那么可能凑出的最大顺子就是(P,P+1,P+2,...,P+k-1),所以我们先检查一下这个P开头的顺子能不能凑出来,如果不能,我们再尝试P-1开头的顺子能不能凑出来......直到试出某个顺子能凑出来。伪代码如下:

for X = p,p-1,p-2,...,0
    if 能凑出 (x,x + 1,x + 2,...,x + k - 1)
        return x + k - 1

以题目样例为例,由于k=5,现有最大整数是13。我们先试(13,14,15,16,17),再试(12,13,14,15,16),......试到(7,8,9,10,11),发现这个顺子能凑出来,因为只有一个9没有,可以用一张百搭卡片凑。

检查X开头的顺子是否能凑出来的算法是,枚举X~(X+K-1)这K个数中,有几个在现有的整数中,有几个不在,需要用百搭卡。如果需要的百搭卡数量超过M,那这个顺子就凑不出来,伪代码如下:

Hashtable <- [A1,A2,...,AN]
need_card = 0
for i = X,X + 1,...,X + k - 1
    if not Hashtable.find(i)
        need_card++;
return need_card <= M

这样整个算法的时间复杂度是O(PK),P是这个数组的最大值,所以有可能有$10^8^$这么大,K最大$10^5^$,显然会超时

优化1

第一个能优化的地方是对于X的枚举,也就是顺子开头的数值。经过分析我们能知道,如果(X,X+1,X+2,...,X+K-1)是能凑出来的最大顺子。那么X一定是存在数,因为如果X是百搭卡变出来的,那么我们为什么百搭卡变成X+K,这样就能凑出来一个更大的顺子(X+1,X+2,...,X+K)

优化2

第二个可以优化的地方就是判断能不能凑出X开头的顺子。我们利用双指针可以把这一步均摊时间复杂度降到O(1)。首先我们对A数组排序,然后对于每一个A[i],我们还是找一个“最优的A[j]”。这里“最优”指最大的A[j]满足A[i]~A[j]之间需要的百搭卡整数不超过M张

image
上图是样例每个Ai对应的最优A[j(绿色箭头)],可以看出当A[i]从大到小枚举的过程中,A[j]也是从大到小改变,不会变大,所以这个双指针枚举的复杂度是O(N)

对于每个A[i],当我们求出最优的A[j]之后,就可以计算以A[i]开头的顺子能不能凑出了。而A[i]~A[j]一共需要的百搭卡是(A[j]-A[i])-(j-i)张,那么剩余的百搭卡一定是用在A[j]+1,A[j]+2...,我们只需要判断剩余的百搭卡是不是足够用到A[i]+k-1即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,m,k;
    vector<int>a;
    cin >> n >> m >> k;
    for(int i = 0;i < n;i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    int ans = -1;
    for(int i = n - 1,j = n - 1;i >= 0;i--)
    {
        int need_card = a[j] - a[i] - (j - i);
        while(need_card > m)
        {
            j--;
            need_card = a[j] - a[i] - (j - i);
        }
        if(a[j] + (m - need_card) - a[i] + 1 >= k)
        {
            ans = a[j] + (m - need_card);
            break;
        }
    }
    cout << ans;
    return 0;
}
最后编辑于: October 19, 2018
Archives Tip
QR Code for this page
Tipping QR Code