问题：在找出长度为m的无序数组b不存在于长度为n的有序数组a中的元素。
a = [1, 2, 3, 4, 5]
b= [1, 9, 3, 7, 5]
输出 [9, 7]
方法一：穷举 m*n
方法二：在a中二分查找，m*logn
方法三：b排序, 求差集 m*longm
具体用方法二还是方法三，看数组长度。
同时介绍对数器：
在笔试中有一个保证正确且容易实现的方法right functin，但是复杂度很高，那么实现它;
同时实现一个样例生成器、实现优化算法f和结果比较算法
同时运行right functin和f，用样例生成器生成大样本，验证优化算法正确性。
具体代码如下
二分查找可以直接 bool binary_serch(a.begin(), b.end(), key);
#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; //生成器 void g(vector<int> &v, int size) { int n = rand() % size + 1; for (int i = 0; i < n; i++) { v.push_back(rand() % 100000007); } } //保证正确，且容易实现的方法 vector<int> rightfunc(vector<int> a, vector<int> b) { vector<int> res; for (int i = 0; i < b.size(); i++) { if (find(a.begin(), a.end(), b[i]) == a.end()) { res.push_back(b[i]); } } return res; } int bin_search(vector<int> a, int l, int r, int key) { if (l <= r) { int mid = (l + r) / 2; if (a[mid] == key) { return mid; } else if (a[mid] > key) { return bin_search(a, l, mid - 1, key); } else { return bin_search(a, mid + 1, r, key); } } return -1; } //方法2 vector<int> f(vector<int> a, vector<int> b) { vector<int> res; for (int i = 0; i < b.size(); i++) { if (bin_search(a, 0, (int)a.size() - 1, b[i]) == -1) { res.push_back(b[i]); } } return res; } void test() { int N = 50; while(N--) { vector<int> a, b; g(a, 100000); g(b, 1000); sort(a.begin(), a.end()); vector<int> res1 = rightfunc(a, b); vector<int> res2 = f(a, b); if (res1 == res2) { cout << N << endl; } else { cout << "error" << endl; } } cout << "OK" << endl; } //方法三 vector<int> f1(vector<int> a, vector<int> b) { sort(b.begin(), b.end()); vector<int> res; int posa = 0, posb = 0; while (posa < a.size() && posb < b.size()) { if (a[posa] < b[posb]) { ++posa; } else if (a[posa] > b[posb]) { ++posb; } else { ++posa; ++posb; } } while (posb < b.size()) { res.push_back(b[posb++]); } return res; } int main() { // test(); vector<int> a, b, res; int N, M, x; cin >> N >> M; for (int i = 0; i < N; i++) { cin >> x; a.push_back(x); } for (int i = 0; i < M; i++) { cin >> x; b.push_back(x); } res = f1(a, b); for (int i = 0; i < res.size(); i++) { cout << res[i] << ' '; } putchar(10); return 0; }
