首页 分享 找出数组a[]中符合a[i]+a[j]=K的数对

找出数组a[]中符合a[i]+a[j]=K的数对

来源:萌宠菠菠乐园 时间:2024-09-13 13:00

最新推荐文章于 2024-02-04 14:21:37 发布

jeanphorn 于 2015-06-19 19:18:11 发布

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

1.问题描述

  在一个整数数组中,元素都为整数,没有重复数。设计一个算法找出满足两个数的和等于k值得数对。例如a[]={1,3,8,6,4}中两个数的和为7的数对为(1,6)和(3,4)。

2. 解决方案

2.1 暴力法

  首先先到的可能就是暴力法,暴力没举出所有的数对然后再判对他们的和是否为K,但这种方法的时间复杂度为O(n^2),效率比较低,一般不可取。代码也就不写了。、

2.2 二分法

  先对数组进行排序,然后使用二分查找算法,使用两个指针分片指向第一个和最后一个元素,然后从两端同时向中间遍历。
  1)、如果a[i] + a[j] > K; 则j–。
  2)、如果a[i] + a[j] = K; 则i++,j–。
  3)、如果a[i] + a[j] < K; 则i++。
  代码如下:
  

int FindCouple(int a[],int n,int k) { int i=0,j=n-1; sort(a,a+n); while(i < j) { if(a[i] + a[j] == k) { printf("(%d,%d)n",a[i],a[j]); i++; j--; } else if(a[i] + a[j] > k) j--; else i++; } return 1; }

1234567891011121314151617181920 2.2 hash方法

  将数组存在hash表中,对每一个数a[i]在hash表中查找K-a[i]是否存在。时间复杂度和空间复杂度都为O(n)。
  

int FindCouple_hash(int a[],int n, int k) { map<int,int> mp; for(int i=0; i < n; i++) mp[a[i]] = 1; for(int i = 0; i < n; i++) if(mp[k-a[i]] == 1) printf("(%d,%d)n",a[i],k-a[i]),mp[a[i]]=0; //相同数对只取一次 return 1; }12345678910111213

相关知识

(●—●)唔姆,余的胸怀不够广阔么?
猫狗收容所
密码 pasuwado题解
宠物疼痛管理:止痛Analgesia
leetcode
虹鳟鱼的营养价值及其在宠物食品中的应用
美国Doublek双K唛得宝K香水
宠物营养I 蛋白质 I 蛋氨酸 I 组氨酸 I 赖氨酸的作用
水分管理对水稻生长期N2O排放的影响
猫狗是如何成为我们家庭一员的?

网址: 找出数组a[]中符合a[i]+a[j]=K的数对 https://www.mcbbbk.com/newsview142245.html

所属分类:萌宠日常
上一篇: 强制使用GPU
下一篇: sin90度=1的证明

推荐分享