算法题29 从一个取值范围为1~N的不重复数列中找出所有满足两数和为N+1的数对 - 在水一方 - 博客频道 - CSDN.NET
题目：一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。复杂度最好是O(n)，如果是O(n2)则不得分。
算法：建立一个map<数列元素值， 对应索引>. 对每个元素i，如果N+1-i不在map中，插入i，否则输出（i, map[i]）.复杂度O(n).
Read full article from 算法题29 从一个取值范围为1~N的不重复数列中找出所有满足两数和为N+1的数对 - 在水一方 - 博客频道 - CSDN.NET
No comments:
Post a Comment