数组中元素的距离、共同元素、最值

求数组中元素间的最近距离（一）

问题描述：数组arr[]中存在N个元素（数组中N个元素没有范围），找到这样的a和b，使得abs（a，b）的值最小。

解决思路：这是个比较简单的问题了，思路也很容易想到，只需要将arr进行排序，这时数组中元素的最短距离只可能是相邻的两个元素之间，这个算法的时间复杂度是：O(N*logN)。如果不对数组进行排序，那么就需要枚举数组中的每两个元素了，求出最小距离，时间复杂度是O(N*N)。

#include
#include
#define N 10
int arr[N];
//要注意是绝对值
int minDistance(int arr[],int n)
{
    int min=1000000,temp;
    for(int k=0;k
    {
        temp=abs(arr[k]-arr[k+1]);
        if(min>temp)
            min=temp;
    }
    return min;
}

int main()
{
    for(int i=0;i
    {
        scanf("%d",&arr[i]);
    }
    int min=minDistance(arr,N);
    printf("%d\n",min);
    return 0;
}
/*
-1 4 5 8 23 67 69 70 72 75
1
Press any key to continue

*/

求两个数组中的相同元素 
问题描述：现在有两个已经排好序的整数数组arr1和arr2，找出两个数组中的相同元素。 

解决思路：既然已经排好序了，那么问题就简单了，假设arr1[2]和arr2[4]相等，那么搜索arr1[3]只需要和arr2[5]及以后的元素比较。如果arr1和arr2中元素的个数分别是N和M，那么这个算法的时间复杂度是O(N+M)，不妨先看看代码。 

#include
#define M 10
#define N 15
int A[M];
int B[N];

int commonArray(int A[],int m, int B[],int n)
{
    int i=0,j=0,count=0;
    while(i
    {
        if(A[i]==B[j])
        {
            printf("%d %d\n",A[i],B[j]);
            count++;
            i++;
            j++;
        }
        else if(A[i]
        {
            i++;
        }
        else
        {
            j++;
        }
    }
    return count;
}

int main()
{
    int i;
    for(i=0;i
    {
        scanf("%d",&A[i]);
    }
    for(i=0;i
    {
        scanf("%d",&B[i]);
    }
    int count=commonArray(A,M,B,N);
    printf("\nthe number of array %d\n",count);
    return 0;
}
/*
1 3 5 7 9 10 13 16 18 20
1 4 5 7 9 11 13 16 19 20 24 26 27 28 29

1 3 5 7 9 10 13 16 18 20
1 4 5 7 9 11 13 16 19 20 24 26 27 28 29
1 1
5 5
7 7
9 9
13 13
16 16
20 20

the number of array 7
Press any key to continue


*/

小结：对于这个问题arr1和arr2数组都已经是排好序的，那么如果两个数组都不是排好序的呢？？后来在网上查了点资料，发现这样一个哈希的思路：遍历一遍arr1，建立哈希表，然后遍历一遍arr2，看看哪一个元素存在于哈希表中。这样一来时间复杂度还是O(N+M)，但是多引入了O(N)的空间复杂度。 

求数组中的最大值（最小值）

问题描述：给定一个整数数组arr，找出其中的最大值（最小值）。

解决思路：传统的方法就是遍历一次数组即可得到最大值（最小值），时间复杂度是O（N）；现在说另外一个思路利用二分，即将数组分成元素数目接近相等的两部分，然后分别找到两个部分的的最大值（最小值），最后合并，比较两个部分的最大值（最小值），即可得到最终的最大值（最小值）。

#include
#define N 15
int B[N];
#define max(a,b) (a>b)? a:b
#define min(a,b) (a

struct node
{
    int max,min;
};

struct node MaxandMin(int B[],int l,int r)
{
    struct node num;
    //递归必定要设定返回条件
    if(l==r)//l与r之间只有一个元素
    {
        num.max=B[l];
        num.min=B[r];
        return num;
    }
    else if(l+1 == r)
    {
        if(B[l]>B[r])
        {
            num.max=B[l];
            num.min=B[r];
        }
        else
        {
            num.max=B[r];
            num.min=B[l];
        }
        return num;
    }

    int mid=(l+r)/2;
    //int lmin,lmax,rmin,rmax;
    struct node lnode,rnode;
    lnode=MaxandMin(B,l,mid);
    rnode=MaxandMin(B,mid+1,r);
    num.min=min(lnode.min,rnode.min);
    num.max=max(lnode.max,rnode.max);
    return num;
}

int main()
{
    for(int i=0;i
    {
        scanf("%d",&B[i]);
    }
    struct node num=MaxandMin(B,0,N-1);
    printf("%d %d\n",num.min,num.max);
    return 0;
}
/*
1 4 5 7 9 11 13 16 19 20 24 26 27 28 29
1 29
Press any key to continue
*/