本实验主要用二分法来查找两个数组中不同的元素
#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; }