二分算法实例应用(二)

简介: 二分法实例应用(二):和为给定数(POJ 4143)

二分算法实例应用(二)

和为给定数 (POJ 4143)

Description

给出若干个整数,询问其中是否有一对数的和等于给定的数。

Input

共三行:

第一行是整数n(0 < n <= 100,000),表示有n个整数。

第二行是n个整数。整数的范围是在0到10^8之间。

第三行是一个整数m(0 <= m <= 2^30),表示需要得到的和。

Output

若存在和为m的数对,输出两个整数,小的在前,大的在后,中间用单个空格隔开。若有多个数对满足条件,选择数对中较小的数更小的。若找不到符合要求的数对,输出一行No。

Sample Input

4
2 5 1 4
6

Sample Output

1 5




算法思想:

  1. 法一

    首先想到暴力破解,采用两重循环,枚举所有可能的取数方法。

    时间复杂度不难得到为O(n^2)。b

    因为本题问题规模达到了十万,若采用暴力破解则会有100亿的数据规模,基本在所有的OJ中都会超时,所以不可取。

  2. 法二

    既然是要找两个数据满足a+b=m,那么我们可以固定一个值a,在数组中找数m-a,若数组为有序数组,那么在数组中查找一个给定数就可以采用二分查找法来降低时间复杂度。

    因此,

    1. 首先我们需对题中输入数组进行排序,可采用快速排序,时间复杂度为O(n logn);
    2. 其次,依次固定前n-1个数据,对每一个数据a进行一轮循环判断,判断是否有元素为c-a。每一轮判断中可以采用二分查找法进行搜索判定。因此本步时间复杂度为O(n log2 n)。

    综上,总体时间复杂度为O(nlogn)。

  3. 法三

    法三是对法二进行的一个优化,在编写法二的程序时,突然想到:既然都是比较数,那和快速排序中一趟的划分关键步骤岂不是有异曲同工之妙嘛,即将大于枢轴元素的元素移至枢轴右侧,将所有小于枢轴元素的元素移至枢轴左侧。在这样的思想下,产生了对法二的进一步优化。

    即:

    1. 同样需要对输入数据进行排序,采用快速排序,时间复杂度为O(nlogn)。关于排序的时间复杂度在目前能力范围内无法优化。
    2. 对于寻找两个数满足a+b=m这一步,可以考虑:设a为最小元素,即数组左端点;b为最大元素,即数组右端点。

      若(a+b)>m,那么表明,两数之和过大,应该减少最大值,使右端点左移,来减少两数之和。

      若(a+b)<m,那么表明,两数之和过小,应该增大最小值,使左端点右移,来增加两数之和。

      若(a+b)=m,那么便找到了一个解。

      这样的算法在找满足a+b=m的步骤中最多只需遍历一遍数组即可得出解,或判断出是否无解,则本步中时间复杂度为O(n)

    综上,总体时间复杂度为O(nlogn)+O(n)=O(nlogn)。虽然总体时间复杂度没有得到改善,但改善了局部的时间复杂度,比之法二,该算法有更好的性能。




代码逻辑:

  1. 法一

    在算法思想章节中已基本概述清楚,由于本算法并未对数据进行任何排序处理,所以得到的解是无序的,但题中要求输出的两个整数,应小的在前,大的在后,若有多个数对满足条件,选择数对中较小的数更小的。所以在求解时,应求尽所有的解,再判断时候满足题设解的条件。

    具体逻辑较为简单不再赘述,代码中有详细说明。

    代码如下:

    void fun1(int n, int *a, int m) {
        int left = 1e8 + 1, right = 1e8 + 1;//left为组合数据中较小的一个
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] + a[j] == m) {//成功找到一组数据满足要求
                    if (a[i] < left || a[j] < left) {//判断是否为最小的组合数据
                        if (a[i] < a[j]) {//组合数据中值较小的放左边
                            left = a[i];
                            right = a[j];
                        } else {
                            left = a[j];
                            right = a[i];
                        }
                    }
                    break;
                }
            }
        }
        if (left == 1e8 + 1)
            printf("No");//若无解则输出No
        else
            printf("%d %d", left, right);//优先输出值较小的组合数据
    }
  2. 法二

    1. 首先对输入数组进行快速排序,为便于读着理解,本文采用手写递归快排算法,若读者已经理解快排本质及其运行逻辑,可采用C/C++排序库函数进行排序。
    2. 快排的基本思想是基于分治法的:在待排序的表中任取一个元素pivot作为枢轴元素,通过一趟排序将待排序表划分为两部分,即:左侧,pivot,右侧,左侧元素为所有小于pivot的元素集合,右侧元素为所有大于pivot的元素集合。通过这个一趟快速排序确定了pivot元素在整个数据表中的最终位置,再依次递归的对左侧数据集合进行快排、右侧数据集合进行快排,直至每部分只剩下一个元素或者为空时为止,即表明此时所有元素都放在了最终位置上。

      //快排主函数
      void QuickSort(int a[], int low, int high) {
          if (low < high) {//递归终止条件
              int pivotPos = Partition(a, low, high);//划分一次,同时确定一个数的位置
              QuickSort(a, low, pivotPos - 1);//对该数左边所有元素进行快排
              QuickSort(a, pivotPos + 1, high);//对该数右边边所有元素进行快排
          }
      }

      一趟快排的划分函数的过程,就是一个交替搜索和交换的过程,划分的效率取决于枢轴元素的选取。

      读者可自行通过Data Structure Visualizations工具进行模拟,理解其精髓本质与运行逻辑。

      https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

      //一趟划分函数
      int Partition(int a[], int low, int high) {
          int pivot = a[low];//将当前表中第一个元素作为枢轴,对表进行划分
          while (low < high) {//循环终止条件
              while (low < high && a[high] >= pivot)high--;//从右往左找第一个小于枢轴元素的元素
              a[low] = a[high];//将小于枢轴元素的元素移至枢轴左侧
              while (low < high && a[low] <= pivot)low++;//从左往右找第一个大于枢轴元素的元素
              a[high] = a[low];//将大于枢轴元素的元素移至枢轴右侧
          }
          a[low] = pivot;//枢轴元素位置确定
          return low;//返回枢轴元素最终位置
      }
    3. 对数据排序完成后,开始依次固定前n-1个数,假设当前为第i个数据元素,此时应对区间[i+1,n]内的数据元素进行二分查找,判断是否有元素满足b=m-a;若有元素满足,则此时的i必为最优解,因为已经对数据进行过排序,i必为最小的解。若区间[i+1,n]内数据元素不存在元素满足b=m-a时,表明当前的第i个元素不为解,应判断下一元素,即i++,直至找到一个解时,退出函数。若当遍历完所以的元素时仍为找到一个解则表明无解。

      代码如下:

      void fun2(int n, int *a, int m) {
          QuickSort(a, 0, n - 1);//将题设数组进行快速排序
          //依次遍历从0~n-1的每一个数据元素,采用二分法查找元素(m - a[i])
          for (int i = 0; i < n - 1; i++) {
              int left = i + 1, right = n;//因为此时为有序数组,所以对区间[i+1,n]进行二分查找
              while (left <= right) {
                  int mid = left + (right - left) / 2;
                  int temp = m - a[i];
      
                  if (temp == a[mid]) {
                      //找到该元素,输出,且由于有序数组,第一个找到的解必为最终解,无须再做法一中的额外判断
                      printf("%d %d", a[i], a[mid]);
                      return;
                  } else if (temp > a[mid]) {//当前中点值小于目标值,修改区间左端点
                      left = mid + 1;
                  } else {//当前中点值大于目标值,修改区间右端点
                      right = mid - 1;
                  }
              }
          }
          printf("No");//若无解则输出No
      }
  3. 法三

    1. 同法二,首先进行快速排序,不再赘述
    2. 对数据排序完成后,由上述算法思想可知,应记录解的区间的左右端点,left=0,right=n-1;通过判断左右端点的元素之和是否与m相等来确定是否为解,记temp=a[left] + a[right];

      • 若 temp = m 则表明找到了解,应输出解
      • 若 temp > m 则表明左右端点之和过大,应减少较大的值,即将右端点左移
      • 若 temp < m 则表明左右端点之和过小,应增加较小的值,即将左端点右移

        每次第边界移动后修改temp的值,再循环判断是否满足 temp = m ,直至找到一个解。

      代码如下:

      //借用快排中划分方法中的思想对法二进行进一步优化
      void fun3(int n, int *a, int m) {
          QuickSort(a, 0, n - 1);//将题设数组进行快速排序
      
          int left = 0, right = n - 1;//记录可能的值的左右区间端点
          int temp = a[left] + a[right];//temp记录区间左右端点元素的和
          while (left < right && (temp != m)) {//若区间合理且temp≠m,进行边界移动
              if (temp > m) {//若temp>m则表明左右端点之和过大,应减少较大的值,即将右端点左移
                  right--;
              }
              if (temp < m) {//若temp<m则表明左右端点之和过小,应增加较小的值,即将左端点右移
                  left++;
              }
              temp = a[left] + a[right];//修改左右端点之和用作下一次判断
          }
      
          if (left < right) {//若left < right,则表明找到了一个区间的左右端点使得其和temp=m;
              printf("%d %d", a[left], a[right]);
          } else {//若left < right,则表明无解,则输出No
              printf("No");
          }
      }




代码整合:

//
// Created by Ss1Two on 2023/2/7.
//

#include "stdio.h"


void fun1(int n, int *a, int m);//法一

void fun2(int n, int *a, int m);//法二

void fun3(int n, int *a, int m);//法三

void QuickSort(int a[], int low, int high);//快速排序函数声明

int Partition(int a[], int low, int high);//快速排序一趟划分函数声明

int main(void) {
    int n, arr[100000], m;
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf_s("%d", &arr[i]);
    }
    scanf_s("%d", &m);


//    fun1(n, arr, m);
//    fun2(n, arr, m);
    fun3(n, arr, m);
    return 0;
}

void fun1(int n, int *a, int m) {
    int left = 1e8 + 1, right = 1e8 + 1;//left为组合数据中较小的一个
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == m) {//成功找到一组数据满足要求
                if (a[i] < left || a[j] < left) {//判断是否为最小的组合数据
                    if (a[i] < a[j]) {//组合数据中值较小的放左边
                        left = a[i];
                        right = a[j];
                    } else {
                        left = a[j];
                        right = a[i];
                    }
                }
                break;
            }
        }
    }
    if (left == 1e8 + 1)
        printf("No");//若无解则输出No
    else
        printf("%d %d", left, right);//优先输出值较小的组合数据
}

void fun2(int n, int *a, int m) {
    QuickSort(a, 0, n - 1);//将题设数组进行快速排序
    //依次遍历从0~n-1的每一个数据元素,采用二分法查找元素(m - a[i])
    for (int i = 0; i < n - 1; i++) {
        int left = i + 1, right = n;//因为此时为有序数组,所以对区间[i+1,n]进行二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int temp = m - a[i];

            if (temp == a[mid]) {
                //找到该元素,输出,且由于有序数组,第一个找到的解必为最终解,无须再做法一中的额外判断
                printf("%d %d", a[i], a[mid]);
                return;
            } else if (temp > a[mid]) {//当前中点值小于目标值,修改区间左端点
                left = mid + 1;
            } else {//当前中点值大于目标值,修改区间右端点
                right = mid - 1;
            }
        }
    }
    printf("No");//若无解则输出No
}

//借用快排中划分方法中的思想对法二进行进一步优化
void fun3(int n, int *a, int m) {
    QuickSort(a, 0, n - 1);//将题设数组进行快速排序

    int left = 0, right = n - 1;//记录可能的值的左右区间端点
    int temp = a[left] + a[right];//temp记录区间左右端点元素的和
    while (left < right && (temp != m)) {//若区间合理且temp≠m,进行边界移动
        if (temp > m) {//若temp>m则表明左右端点之和过大,应减少较大的值,即将右端点左移
            right--;
        }
        if (temp < m) {//若temp<m则表明左右端点之和过小,应增加较小的值,即将左端点右移
            left++;
        }
        temp = a[left] + a[right];//修改左右端点之和用作下一次判断
    }

    if (left < right) {//若left < right,则表明找到了一个区间的左右端点使得其和temp=m;
        printf("%d %d", a[left], a[right]);
    } else {//若left < right,则表明无解,则输出No
        printf("No");
    }
}

//快排主函数
void QuickSort(int a[], int low, int high) {
    if (low < high) {//递归终止条件
        int pivotPos = Partition(a, low, high);//划分一次,同时确定一个数的位置
        QuickSort(a, low, pivotPos - 1);//对该数左边所有元素进行快排
        QuickSort(a, pivotPos + 1, high);//对该数右边边所有元素进行快排
    }
}

//一趟划分
int Partition(int a[], int low, int high) {
    int pivot = a[low];//将当前表中第一个元素作为枢轴,对表进行划分
    while (low < high) {//循环终止条件
        while (low < high && a[high] >= pivot)high--;//从右往左找第一个小于枢轴元素的元素
        a[low] = a[high];//将小于枢轴元素的元素移至枢轴左侧
        while (low < high && a[low] <= pivot)low++;//从左往右找第一个大于枢轴元素的元素
        a[high] = a[low];//将大于枢轴元素的元素移至枢轴右侧
    }
    a[low] = pivot;//枢轴元素位置确定
    return low;//返回枢轴元素最终位置
}

Created by Ss1Two on 2023/2/7

目录
相关文章
|
2月前
|
存储 监控 JavaScript
基于布隆过滤器的 Node.js 算法在局域网电脑桌面监控设备快速校验中的应用研究
本文探讨了布隆过滤器在局域网电脑桌面监控中的应用,分析其高效空间利用率、快速查询性能及动态扩容优势,并设计了基于MAC地址的校验模型,提供Node.js实现代码,适用于设备准入控制与重复数据过滤场景。
92 0
|
22天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
145 3
|
1月前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
|
1月前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
1月前
|
机器学习/深度学习 算法 安全
小场景大市场:猫狗识别算法在宠物智能设备中的应用
将猫狗识别算法应用于宠物智能设备,是AIoT领域的重要垂直场景。本文从核心技术、应用场景、挑战与趋势四个方面,全面解析这一融合算法、硬件与用户体验的系统工程。
|
3月前
|
机器学习/深度学习 人工智能 算法
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习模型、算法与应用的全方位解析
深度学习,作为人工智能(AI)的一个重要分支,已经在多个领域产生了革命性的影响。从图像识别到自然语言处理,从语音识别到自动驾驶,深度学习无处不在。本篇博客将深入探讨深度学习的模型、算法及其在各个领域的应用。
579 3
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
88 1
|
2月前
|
算法 数据可视化
matlab版本粒子群算法(PSO)在路径规划中的应用
matlab版本粒子群算法(PSO)在路径规划中的应用
|
3月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中,企业面临员工泄密风险。本文探讨使用跳表(Skip List)数据结构优化泄密防护系统,提升敏感数据监测效率。跳表以其高效的动态数据处理能力,为企业信息安全管理提供了可靠技术支持。
88 0

热门文章

最新文章