求交集程序怎么写好看

时间:2025-01-26 19:58:33 单机游戏

求两个集合的交集可以通过多种方法实现,下面我将介绍几种常见的方法,并提供相应的代码示例。

方法一:排序加双指针

这是一种简单且高效的方法,首先对两个集合进行排序,然后使用双指针技术找到交集。

```cpp

include

include

include

std::vector intersection(std::vector& nums1, std::vector& nums2) {

std::sort(nums1.begin(), nums1.end());

std::sort(nums2.begin(), nums2.end());

std::vector result;

int i = 0, j = 0;

while (i < nums1.size() && j < nums2.size()) {

if (nums1[i] == nums2[j]) {

// 保证加入元素的唯一性

if (result.empty() || result.back() != nums1[i]) {

result.push_back(nums1[i]);

}

i++;

j++;

} else if (nums1[i] < nums2[j]) {

i++;

} else {

j++;

}

}

return result;

}

int main() {

std::vector nums1 = {1, 2, 2, 1};

std::vector nums2 = {2, 2};

std::vector result = intersection(nums1, nums2);

for (int num : result) {

std::cout << num << " ";

}

return 0;

}

```

方法二:使用集合

如果你使用的是Python,可以直接利用集合(set)的操作来求交集。

```python

def intersection(nums1, nums2):

return list(set(nums1) & set(nums2))

nums1 = [1, 2, 2, 1]

nums2 = [2, 2]

result = intersection(nums1, nums2)

print(result)

```

方法三:冒泡排序法

这种方法通过冒泡排序的思想来找到交集,虽然简单,但效率不高。

```cpp

include

include

std::vector intersection(std::vector& nums1, std::vector& nums2) {

std::vector result;

int k = 0;

for (int i = 0; i < nums1.size(); i++) {

for (int j = 0; j < nums2.size(); j++) {

if (nums1[i] == nums2[j]) {

result.push_back(nums1[i]);

k++;

break; // 避免重复添加相同的元素

}

}

}

return result;

}

int main() {

std::vector nums1 = {3, 8, 9, 22};

std::vector nums2 = {3, 5, 7, 9, 55};

std::vector result = intersection(nums1, nums2);

for (int num : result) {

std::cout << num << " ";

}

return 0;

}

```

总结

以上是几种求交集的方法,你可以根据具体需求和数据规模选择合适的方法。排序加双指针方法在时间和空间复杂度上都有较好的表现,而使用集合的方法则更为简洁。冒泡排序法虽然简单,但在处理大数据集时效率较低。