本实验主要用二分法来查找两个数组中不同的元素
#include<iostream>
using namespace std;
int* GetAllNotIncluded(int A[], int a_length, int B[], int b_length);
int main()
{
int arr1[6] = { 1,2,3,4,5,6, };
int arr2[3] = { 8, 9, 1 };
int *arr3;
arr3 = GetAllNotIncluded(arr1, 6, arr2, 3);
for (int i = 0; i<sizeof(arr2)/sizeof(int); i++)
cout << arr3[i]<<' ';
cin.get(); //暂停窗口,没有其他意义
return 0;
}
int* GetAllNotIncluded(int A[],int a_length, int B[],int b_length) { //二分法查找不同的数据
int k = 0;
int *res = new int[]; //声明一个数据指针
for (int i = 0; i < b_length; i++) {
int l = 0;
int r = a_length - 1;
bool contains = false;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (A[mid] == B[i]) {
contains = true;
break;
}
if (A[mid] > B[i]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
if (!contains) { //存储不相同的数据
res[k] = B[i];
k += 1;
}
}
return res;
}
本实验有两个不足:
第一没法知道返回的指针数组的大小,导致用了
这样的表述
第二在子函数中不能用
sizeof(A)/sizeof(int)
来求数组的长度
例如:
int* GetAllNotIncluded(int A[], int B[]) { //二分法查找不同的数据
int k = 0;
int *res = new int[]; //声明一个数据指针
for (int i = 0; i < sizeof(B)/sizeof(int); i++) {
int l = 0;
int r = sizeof(A)/sizeof(int)- 1;
bool contains = false;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (A[mid] == B[i]) {
contains = true;
break;
}
if (A[mid] > B[i]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
if (!contains) { //存储不相同的数据
res[k] = B[i];
k += 1;
}
}
return res;
}
这样写得出来的A的长度只有1.
欢迎大神赐教,O(∩_∩)O谢谢。
优化:
#include<iostream>
using namespace std;
int* GetAllNotIncluded(int A[], int a_length, int B[], int b_length);
int main()
{
int arr1[6] = { 1, 2, 3, 4, 5, 6, };
int arr2[3] = { 4, 1, 5 };
int *arr3;
arr3 = GetAllNotIncluded(arr1, 6, arr2, 3);
int ans = 1;
int End_Flag= 0;
while (ans)
{
ans = arr3[End_Flag];
End_Flag++;
}
for (int i = 0; i<End_Flag-1; i++)
cout << arr3[i] << ' ';
cin.get(); //暂停窗口,没有其他意义
return 0;
}
int* GetAllNotIncluded(int A[], int a_length, int B[], int b_length) { //二分法查找不同的数据
int k = 0;
int *res = new int[]; //声明一个数据指针
for (int i = 0; i < b_length; i++) {
int l = 0;
int r = a_length - 1;
bool contains = false;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (A[mid] == B[i]) {
contains = true;
break;
}
if (A[mid] > B[i]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
if (!contains) { //存储不相同的数据
res[k] = B[i];
k += 1;
}
}
res[k] = NULL; //数据帧尾标志
return res;
}
方法2:顺序查找
#include <iostream>
using namespace std;
//顺序查找算法,时间复杂度为O(n),额外空间复杂度为O(1)
//特点:如果同时有多个命中元素时,只返回最大值;如果查找失败时返回-1
template <typename T>int find(T e, T arr[], int low, int high) //C++中模板
{
while ((low < high--) && (e != arr[high]));
return high;
}
int main()
{
int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << find(5, arr, 0, 9) << endl;
return 0;
}
原文链接: https://www.cnblogs.com/panlangen/p/7857591.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/263625
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!