给定两个整型数组,本题要求找出不是两者共有的元素。
时间: 2023-11-29 07:11:59 浏览: 153
解法1:暴力枚举
对于第一个数组中的每个元素,都在第二个数组中查找是否存在相同的元素。时间复杂度为O(n^2)。
解法2:哈希表
使用哈希表存储第一个数组中的所有元素,然后遍历第二个数组,查找在哈希表中是否存在相同的元素。时间复杂度为O(n),但需要额外的空间来存储哈希表。
解法3:排序+双指针
对两个数组进行排序,然后使用双指针分别指向两个数组的开头,比较两个指针指向的元素大小。若相等,则两个指针同时向后移动;若第一个数组中的元素小,则第一个指针向后移动;否则第二个指针向后移动。时间复杂度为O(nlogn),不需要额外的空间。
代码实现:
解法1:
int findDifferent(int a[], int b[], int n, int m) {
for (int i = 0; i < n; i++) {
bool found = false;
for (int j = 0; j < m; j++) {
if (a[i] == b[j]) {
found = true;
break;
}
}
if (!found) {
return a[i];
}
}
return -1; // 未找到
}
解法2:
int findDifferent(int a[], int b[], int n, int m) {
unordered_set<int> s;
for (int i = 0; i < n; i++) {
s.insert(a[i]);
}
for (int i = 0; i < m; i++) {
if (s.find(b[i]) == s.end()) {
return b[i];
}
}
return -1; // 未找到
}
解法3:
int findDifferent(int a[], int b[], int n, int m) {
sort(a, a + n);
sort(b, b + m);
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] == b[j]) {
i++;
j++;
} else if (a[i] < b[j]) {
return a[i];
} else {
return b[j];
}
}
return i == n ? b[j] : a[i];
}