枚举+优化(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 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Tensorflow自学之前的bigpicture

作者:数据娃掘 来源:http://blog.csdn.net/jdbc/article/details/68957085 前言 目前,深度学习在计算机科学各领...

3387
来自专栏人工智能

将图像转换位mnist数据格式

利用mnist数据对数字符号进行识别基本上算是深度学习的Hello World了。在我学习这个“hello world”的过程中,总感觉缺点什么,于是发现无论是...

27110
来自专栏null的专栏

挑战数据结构和算法面试题——最大间隔

题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。 ? 分析: 本题首先需要理解清楚最大间隔的最小: 最初的间隔为:[1,1,4,1],此时最大间隔为4 删...

2683
来自专栏性能与架构

算法中描述复杂度的大O是什么意思?

简介 算法是解决问题的方法,通常一个问题会有多种解决方法,就是有多种算法,那么我们如何决定哪个算法更好或者更高效呢? 为了描述一个算法的效率,就用到了这个大O,...

2965
来自专栏人工智能LeadAI

TensorFlow从0到1丨第2篇:TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Ten...

3824
来自专栏企鹅号快讯

动态神经网络工具包Dynet

作者|Murat 译者|陈亮芬 编辑|Emily 基于诸如 TensorFlow 等几种流行工具包的编程模型使用的是静态声明方法,这些工具包将网络架构的声明和执...

2457
来自专栏漫漫深度学习路

pytorch学习笔记(九):PyTorch结构介绍

PyTorch结构介绍 对PyTorch架构的粗浅理解,不能保证完全正确,但是希望可以从更高层次上对PyTorch上有个整体把握。水平有限,如有错误,欢迎指错,...

2236
来自专栏机器之心

教程 | 维度、广播操作与可视化:如何高效使用TensorFlow

选自GitHub 机器之心编译 参与:Nurhachu Null、李泽南 本文从 Tensorflow 基础、理解静态维度和动态维度、广播操作(Broading...

4135
来自专栏WindCoder

TensorFlow入门:一篇机器学习教程

TensorFlow是一个由Google创建的开源软件库,用于实现机器学习和深度学习系统。这两个名称包含一系列强大的算法,它们共享一个共同的挑战——让计算机学习...

971
来自专栏AI科技评论

开发 | 这才是 TensorFlow 自带可视化工具 TensorBoard 的正确打开方式!(附项目源码)

AI科技评论按:本文作者 Jerry,原文载于作者个人博客,AI科技评论已获授权。 TensorBoard 如何更直观的观察数据在神经网络中的变化,或是已经构建...

3766

扫码关注云+社区