从二维向量中筛选第二元素未出现在另一对首元素中的数对

要解决这个问题——从二维向量里挑出所有数对，要求该数对的第二个元素没有出现在任何其他数对的第一个位置，可以用「先收集、后筛选」的思路，效率和可读性都不错：

核心步骤 #

• 第一步：把所有数对的第一个元素存到一个集合里，集合的快速查找特性能帮我们节省判断时间。
• 第二步：遍历原二维向量，逐个检查每个数对的第二个元素是否不在这个集合里，符合条件的就保留。

C++ 实现示例 #

#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

vector<vector<int>> filterValidPairs(const vector<vector<int>>& inputPairs) {
    unordered_set<int> firstElementSet;
    
    // 收集所有数对的第一个元素
    for (const auto& pair : inputPairs) {
        if (pair.size() >= 2) { // 跳过不完整的数对
            firstElementSet.insert(pair[0]);
        }
    }
    
    vector<vector<int>> validPairs;
    // 筛选符合条件的数对
    for (const auto& pair : inputPairs) {
        if (pair.size() >= 2 && !firstElementSet.count(pair[1])) {
            validPairs.push_back(pair);
        }
    }
    
    return validPairs;
}

// 测试用例
int main() {
    vector<vector<int>> testPairs = {{1,2}, {2,3}, {3,4}, {5,6}};
    vector<vector<int>> result = filterValidPairs(testPairs);
    
    cout << "符合条件的数对：\n";
    for (const auto& p : result) {
        cout << "[" << p[0] << ", " << p[1] << "]\n";
    }
    // 输出：[3,4]、[5,6]，因为4和6没出现在任何数对的第一个元素里
    return 0;
}

Python 实现示例 #

如果用Python处理列表（对应二维向量），逻辑完全一致，代码更简洁：

def filter_valid_pairs(pairs):
    # 收集所有有效数对的第一个元素
    first_elements = {pair[0] for pair in pairs if len(pair) >= 2}
    # 筛选符合条件的数对
    return [pair for pair in pairs if len(pair) >= 2 and pair[1] not in first_elements]

# 测试
test_pairs = [[1,2], [2,3], [3,4], [5,6]]
print(filter_valid_pairs(test_pairs))  # 输出 [[3, 4], [5, 6]]

关键细节说明 #

• 用集合存储第一个元素：不管是C++的unordered_set还是Python的set，查找操作的平均时间复杂度都是O(1)，比遍历列表查找的O(n)高效得多，数据量越大优势越明显。
• 加入数对完整性判断：避免处理只有单个元素的子向量，防止数组越界或者错误判断。

内容的提问来源于stack exchange，提问作者Aryan Singhal