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

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

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

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

双指针优化

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

 当红色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

 从上面的图我们可以看出:当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

思路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张

 上图是样例每个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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

实现属于自己的TensorFlow(一) - 计算图与前向传播

前言 前段时间因为课题需要使用了一段时间TensorFlow,感觉这种框架很有意思,除了可以搭建复杂的神经网络,也可以优化其他自己需要的计算模型,所以一直想自...

4177
来自专栏专知

【附源码】TensorFlow动态图(Eager模式)的那些神坑

导读:TensorFlow的动态图(Eager模式)为TensorFlow提供了Pythonic的API,让开发者可以像使用PyTorch一样使用TensorF...

872
来自专栏人工智能LeadAI

Python 设计模式初探

本文章是在阅读精通Python设计模式(中文版)(https://book.douban.com/subject/26829015/),以及阅读 Mask R-...

3546
来自专栏tkokof 的技术,小趣及杂念

一种稀疏矩阵的实现方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/tkokof1/article/details/828...

951
来自专栏python3

python语句-中断循环-continue,break

continue的作用是:从continue语句开始到循环结束,之间所有的语句都不执行,直接从一下次循环重新开始

913
来自专栏数据结构与算法

五校联考模拟赛Day2T2矩阵(容斥原理)

设$f[i][j]$表示到了第$i$行,已经有$j$列被染黑,然后暴力转移上一行有几个黑格子

901
来自专栏专注数据中心高性能网络技术研发

HERD--位运算

判断一个数是否是2的次方 1 static inline int hrd_is_power_of_2(uint32_t n) 2 { 3 retur...

3549
来自专栏程序员互动联盟

【编程概念】--随机数

在编程的过程中经常遇到需要生成随机数的问题,其实这个就是引用系统自带的随机数函数产生数值来使用。 C/C++怎样产生随机数:这里要用到的是rand()函数, s...

35815
来自专栏深度学习之tensorflow实战篇

tensorflow(一)windows 10 64位安装tensorflow1.4与基本概念解读tf.global_variables_initializer

一.安装 目前用了tensorflow、deeplearning4j两个深度学习框架, tensorflow 之前一直支持到python 3.5,目前以更新...

3656
来自专栏云时之间

小白笔记——R语言(1)

最近一段时间的R语言学习笔记,以便于自己学习之用,特记录在博客中,感兴趣的人还可以看看。记录的东西也不一定正确,请大家指教,里面可能会引用到一些别人的资料等,作...

3339

扫码关注云+社区