#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
// 想要的功能，给定范围，给定个数，生成一个带有随机数的数组
void Generate(int **ptr, int length, int high){
*ptr = malloc(sizeof(int)*length);
if(*ptr){
int rand_num;
for(int i=0;i<length;i++){
rand_num = rand() % high; // 生成[0,high)的随机数
*(*ptr+i) = rand_num; // *ptr是首地址
}
}
else{
printf("Application for space failed!");
}
}
// 交换两块内存中的值
void Swap(void *first, void *second, size_t size){
// 得到传进来的类型，利用其开辟一块相同大小的空间
void *temp = malloc(sizeof(void *)*size);
// 然后将值复制到那块空间中，执行交换操作
if(temp){
memcpy(temp,first,size); // 目的地，源，复制多少块内存
memcpy(first,second,size);
memcpy(second,temp,size);
}
else{
puts("Application for space failed!");
}
}
// 冒泡排序
void BubbleSort(int *array, int length){
int i,j;
for(i=length-1;i>0;i--){
for(j=0;j<i;j++){
if(*(array+j) > *(array+j+1)){
Swap(array+j, array+j+1, 1);
}
}
}
}
// 找到B中的所有不在A的元素
void FindDifferenceFirst(int *arrayA, int *arrayB,int length_a, int length_b){
int i,j;
for(i=0;i<length_b;i++){
for(j=0;j<length_a;j++){
if(*(arrayB+i) == *(arrayA+j)){ // 如果B中元素在A中找到了，直接跳转到B数组中下一个元素
break;
}else if(j==length_a-1){ // 如果遍历到A数组最后一个元素，而且两者还不相等
printf("%d " ,*(arrayB+i));
}
}
}
}
int main()
{
srand(time(NULL)); // 每次随机出来的数不一样
int length_a = 10;
int high_a = 20;
int *arrayA; // 创建数组A
Generate(&arrayA, length_a, high_a);
BubbleSort(arrayA, length_a); // A数组有序
int length_b = 15;
int high_b = 20;
int *arrayB; // 创建数组B，无序数组
Generate(&arrayB, length_b, high_b);
int i;
// 打印A数组
printf("A数组：\n");
for(i=0;i<length_a;i++){
printf("%d ", *(arrayA+i));
}
// 打印B数组
printf("\nB数组：\n");
for(i=0;i<length_b;i++){
printf("%d ", *(arrayB+i));
}
printf("\nB中所有不在A的元素：\n");
FindDifferenceFirst(arrayA,arrayB,length_a,length_b);
return 0;
}
2）第二种算法流程的提出是因为 A 是有序数组，有序数组二分查找的时间复杂度是 O(logn)（所有A查找一遍的复杂度是 O(logN) ），遍历数组 B 的时间复杂度为 O(M)，所有总的时间复杂度是 O(MlogN)
// 二分查找
int BinarySearch(int number, int *array, int length){
int low = 0;
int high = length-1;
while(low <= high){
int middle = low + (high-low)/2;
if(number < *(array+middle)){
high = middle-1;
}else if(number > *(array+middle)){
low = middle+1;
}else{
return *(array+middle);
}
}
return -1;
}
void FindDifferenceSecond(int *arrayA, int *arrayB,int length_a, int length_b){
int i,j;
for(i=0;i<length_b;i++){
int result = BinarySearch(*(arrayB+i), arrayA, length_a);
if(result == -1){ // 等于-1代表A中没有这个数
printf("%d, ", *(arrayB+i));
}
}
}
int main()
{
srand(time(NULL)); // 每次随机出来的数不一样
int length_a = 10;
int high_a = 20;
int *arrayA; // 创建数组A
Generate(&arrayA, length_a, high_a);
BubbleSort(arrayA, length_a); // A数组有序
int length_b = 15;
int high_b = 20;
int *arrayB; // 创建数组B，无序数组
Generate(&arrayB, length_b, high_b);
int i;
// 打印A数组
printf("A数组：\n");
for(i=0;i<length_a;i++){
printf("%d ", *(arrayA+i));
}
// 打印B数组
printf("\nB数组：\n");
for(i=0;i<length_b;i++){
printf("%d ", *(arrayB+i));
}
printf("\nB中所有不在A的元素：\n");
\\ FindDifferenceFirst(arrayA,arrayB,length_a,length_b);
printf("\n");
FindDifferenceSecond(arrayA,arrayB,length_a,length_b);
return 0;
}
3）算法流程3，首先 B 数组排序就是 O(MlogM) 的时间复杂度，其次，利用类似外排的方式意思就是，设置两个指标，分别指向 A、B 数组的起始位置，然后逐一比对，哪个数组的元素小，哪个数组的指标就向后移，在移动的过程中进行判断：如果 A 数组中元素比 B 数组元素小，A 数组的指标 ++；如果 B 数组的元素比 A 数组元素相等，B 数组指标 ++；如果 B 数组元素比 A 数组元素小，那么打印该元素，并且 B 数组指标 ++，因为这证明 B 数组之前就没有和 A 数组元素相等的时候；最后判断一下 B 数组是否遍历完毕，因为如果 A 数组值都小于 B 数组，B 数组的指标是没办法移动的，至于 A 数组遍历完毕无所谓，只要 B 中元素都和 A 比较过就行。这样比较下来的时间复杂度是 O(M+N)，所以总时间复杂度为 O(MlogM) + O(M+N)
void FindDifferenceThird(int *arrayA, int *arrayB, int length_a, int length_b){
// 首先将B数组排序
BubbleSort(arrayB,length_b);
int i=0,j=0;
while(i<length_a && j<length_b){
if(*(arrayA+i) < *(arrayB+j)){ // 如果A的元素小
i++;
}else if(*(arrayA+i) == *(arrayB+j)){
j++;
}else if(*(arrayA+i) > *(arrayB+j)){
printf("%d ", *(arrayB+j));
j++;
}
}
// 还要判断一下B数组有没有遍历完，没遍历完说明A数组元素都太小了
while(j<length_b){
printf("%d ", *(arrayB+j));
j++;
}
}
