列表中具有重复项和位置的唯一对
Unique pairs in list with duplicates & position
在准备技术面试时,我的一个朋友遇到了一个有趣的问题:给定一个包含 n 个整数的列表,找到所有相同的对和 return 它们的位置。
Example input: [3,6,6,6,1,3,1]
Expected output: (0,5), (1,2), (1,3), (2,3), (4,6)
Stack Overflow 有大量关于唯一对的存在检查或特殊情况(如无重复)的答案,但我没有找到通用、快速的解决方案。我下面的方法的时间复杂度是 O(n) 最好的情况,但降级到 O(n^2) 最坏的情况(输入值都相同)。
有没有办法将其降低到 O(n*logN) 最坏情况?
// output is a vector of pairs
using TVecPairs= vector<pair<size_t,size_t>>;
TVecPairs findPairs2( const vector<uint32_t> &input )
{
// map keyvalue -> vector of indices
unordered_map<uint32_t, vector<size_t>> mapBuckets;
// stick into groups of same value
for (size_t idx= 0; idx<input.size(); ++idx) {
// append index for given key value
mapBuckets[input[idx]].emplace_back( idx );
}
// list of index pairs
TVecPairs out;
// foreach group of same value
for (const auto &kvp : mapBuckets) {
const vector<size_t> &group= kvp.second;
for (auto itor= cbegin(group); itor!=cend(group); ++itor) {
for (auto other= itor+1; other!=cend(group); ++other) {
out.emplace_back( make_pair(*itor,*other) );
}
}
}
return out;
}
正如其他人所说,它是一个 O(n^2),以防您想要以您提到的方式输出。如果你可以用不同的方式打印它,你可以在 C++ 中用 O(n * (hashmap 的 insertion/read 的复杂性) = O(n*log(n)) 来实现。一些 python 代码描述以上如下:
def dupes(arrlist):
mydict=dict()
count = 0
for x in arrlist:
if mydict.has_key(x):
mydict[x] = mydict[x] + [count]
else:
mydict[x] = [count]
count = count + 1
print mydict
return
对于上面的例子:
>>> dupes([3, 6, 6, 6, 1, 3, 1])
{1: [4, 6], 3: [0, 5], 6: [1, 2, 3]}
在准备技术面试时,我的一个朋友遇到了一个有趣的问题:给定一个包含 n 个整数的列表,找到所有相同的对和 return 它们的位置。
Example input: [3,6,6,6,1,3,1]
Expected output: (0,5), (1,2), (1,3), (2,3), (4,6)
Stack Overflow 有大量关于唯一对的存在检查或特殊情况(如无重复)的答案,但我没有找到通用、快速的解决方案。我下面的方法的时间复杂度是 O(n) 最好的情况,但降级到 O(n^2) 最坏的情况(输入值都相同)。
有没有办法将其降低到 O(n*logN) 最坏情况?
// output is a vector of pairs
using TVecPairs= vector<pair<size_t,size_t>>;
TVecPairs findPairs2( const vector<uint32_t> &input )
{
// map keyvalue -> vector of indices
unordered_map<uint32_t, vector<size_t>> mapBuckets;
// stick into groups of same value
for (size_t idx= 0; idx<input.size(); ++idx) {
// append index for given key value
mapBuckets[input[idx]].emplace_back( idx );
}
// list of index pairs
TVecPairs out;
// foreach group of same value
for (const auto &kvp : mapBuckets) {
const vector<size_t> &group= kvp.second;
for (auto itor= cbegin(group); itor!=cend(group); ++itor) {
for (auto other= itor+1; other!=cend(group); ++other) {
out.emplace_back( make_pair(*itor,*other) );
}
}
}
return out;
}
正如其他人所说,它是一个 O(n^2),以防您想要以您提到的方式输出。如果你可以用不同的方式打印它,你可以在 C++ 中用 O(n * (hashmap 的 insertion/read 的复杂性) = O(n*log(n)) 来实现。一些 python 代码描述以上如下:
def dupes(arrlist):
mydict=dict()
count = 0
for x in arrlist:
if mydict.has_key(x):
mydict[x] = mydict[x] + [count]
else:
mydict[x] = [count]
count = count + 1
print mydict
return
对于上面的例子:
>>> dupes([3, 6, 6, 6, 1, 3, 1])
{1: [4, 6], 3: [0, 5], 6: [1, 2, 3]}