small用于不连续数组_左神直通BAT算法之找出B中不属于A的数
找出B中不属于A的数
找出数组B中不属于A的数，数组A有序而数组B无序。假设数组A有n个数，数组B有m个数，写出算法并分析时间复杂度。
方法一：遍历
首先遍历B，将B中的每个数拿到到A中找，若找到则打印。对应算法如下：
int A[] = {1, 2, 3, 4, 5};
int B[] = {1, 4, 2, 6, 5, 7};
for (int i = 0; i < 6; ++i) {
int temp = B[i];
bool flag = false;
for (int j = 0; j < 5; ++j) {
if (A[j] == temp) {
flag = true; //找到了
break;
}
}
if (!flag) { //没找到
printf("%d", temp);
}
}
不难看出上述算法的时间复杂度为 O(m*n)，因为将两个数组都遍历了一遍
方法二：二分查找
由于数组A是有序的，在一个有序序列中查找一个元素可以使用二分法(也称折半法)。原理就是将查找的元素与序列的中位数进行比较，如果小于则去掉中位数及其之后的序列，如果大于则去掉中位数及其之前的序列，如果等于则找到了。如果不等于那么再将其与剩下的序列继续比较直到找到或剩下的序列为空为止。
利用二分法对应题解的代码如下：
for (int i = 0; i < 6; ++i) { //B的长度为6
int temp = B[i];
//二分法查找
int left = 0,right = 5-1; //A的长度为5
int mid = (left + right) / 2;
while (left < right && A[mid] != temp) {
if (A[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
mid = (left + right) / 2;
}
if (A[mid] != temp) {
printf("%d", temp);
}
}
for循环 m次， while循环 logn次(如果没有特别说明，log均以2为底)，此算法的时间复杂度为 O(mlogn)
方法三：排序+外排
第三种方法就是将数组B也排序，然后使用逐次比对的方式来查找A数组中是否含有B数组中的某元素。引入a、b两个指针分别指向数组A、B的首元素，比较指针指向的元素值，当 a<b时，向后移动a指针查找该元素；当 a=b时，说明A中存在该元素，跳过该元素查找，向后移动b；当 a>b时说明A中不存在该元素，打印该元素并跳过该元素的查找，向后移动b。直到a或b有一个到达数组末尾为止(若a先到达末尾，那么b和b之后的数都不属于A)
对应题解的代码如下：
void fun3(int A[],int a_length,int B[],int b_length){
quickSort(B, 0, b_length - 1); //使用快速排序法对数组B排序->O(mlogm)
int* a = A,*b=B;
while (a <= A + a_length - 1 || b <= B + b_length - 1) {
if (*a == *b) {
b++;
continue;
}
if (*a > *b) {
printf("%d", *b);
b++;
} else {
a++;
}
}
if (a == A + a_length) { //a先到头
while (b < B + b_length) {
printf("%d", *b);
b++;
}
}
}
快速排序的代码如下：
#include
#include
//交换两个int变量的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
//产生一个low~high之间的随机数
int randomInRange(int low, int high){
srand((int) time(0));
return (rand() % (high - low))+low;
}
//快速排序的核心算法，随机选择一个数，将比该数小的移至数组左边，比该数大的移至
//数组右边，最后返回该数的下标(移动完之后该数的下标可能与移动之前不一样)
int partition(int arr[],int start,int end){
if (arr == NULL || start < 0 || end <= 0 || start > end) {
return -1;
}
int index = randomInRange(start, end);//随机选择一个数
swap(arr[index], arr[end]);//将该数暂时放至末尾
int small = start - 1;
//遍历前n-1个数与该数比较并以该数为界限将前n-1个数
//分为两组，small指向小于该数的那一组的最后一个元素
for (index = start; index < end; index++) {
if (arr[index] < arr[end]) {
small++;
if (small != index) {
swap(arr[small], arr[index]);
}
}
}
//最后将该数放至数值较小的那一个组的中间
++small;
swap(arr[small], arr[end]);
return small;
}
void quickSort(int arr[],int start,int end) {
if (start == end) {
return;
}
int index = partition(arr, start, end);
if (index > start) {
quickSort(arr,start, index - 1);
}
if (index < end) {
quickSort(arr, index + 1, end);
}
}
此种方法的时间复杂度为： O(mlogm)(先对B排序)+ O(m+n)(最坏的情况是指针a和b都到头)。
三种方法的比较
O(m*n)O(mlogn)(以2为底)O(mlogm)+O(m+n)(以2为底)
易知算法2比1更优，因为增长率 logn<n。而2和3的比较取决于样本量m和n之间的差距，若 m>>n那么2更优，不难理解：数组B元素较多，那么对B的排序肯定要花费较长时间，而这一步并不是题解所必需的，不如采用二分法；相反地，若 m<<n，那么3更优。
出自：http://www.zhenganwen.top
已获授权
作者是前腾讯员工/现创业公司员工，致力于分享leetcode/剑指offer/算法题解/互联网时事/编程资源，觉得不错关注转发一下。
