首页 > 代码库 > 算法(1)数组

算法(1)数组

写在前面:研究操作系统,习惯了用C,但是在做算法题甚至构建大型系统时,C真的是噩梦。还是用C++比较好,基本算法很成熟,并可基于此实现更复杂的算法。那就边写算法边捡起来好久不用的C++吧!

题目:数组中的k差对(K-diff Pairs)。输入为一个数组A和一个整数k,找到数组中 所有的数值对pairs(i,j),其中A[i]和A[j]之间差的绝对值是k。比如【3,1,4,1,5】,k=2,ouput=2,这样的差值对是(1,3)和(3,5),其中1虽然在数组中出现过2次,但是只算一次。(题目:https://leetcode.com/problems/k-diff-pairs-in-an-array/#/description)

思路:把数组中的元素放到map中,key是数组中的值,value是该值在数组中出现的次数。构建好map之后,遍历数组,看看a[i]+k这个值在数组中是否存在。

答案:https://github.com/honpey/codebox/blob/master/leetcode/array/p532.cpp

为什么要用unordered_map?因为后面涉及到查找,unordered_map查找是不是更慢一些,但是插入时就简单一些;这个题目中数据量不大,所以直接就用unordered_map了。unordered_map使用hash表实现,在只要访问不要排序的场景适用,搜索时间复杂度是O(1);但是map使用RB-tree实现,搜索、插入、删除的时间复杂度都是O(logN),但是这并不是表示unordered_map就一定是好的,还是要看数据量的。unordered_map和hash_map干了一样的事儿,但是hash_map仍没写入C++11里。

相关知识点

C++中数据结构:map,vector,auto变量

当使用到C++11中的结构体时,比如unordered_map时,编译时加上:g++ -std=c++11 -o $@ $<

之前错误思路

算法(1)数组