首页 > 代码库 > 关于数组的一些小算法

关于数组的一些小算法

2024-07-06 03:55:47   224人阅读

1.已知两个有序数组A,B，将它们合并为一个有序数组。利用到的是归并算法的思想。

int* combine(int a[],int n1,int b[],int n2)
{
    int i = 0,j = 0,k = 0;
    int *c = new int[n1+n2];
    while(i<n1&&j<n2)   //依次比较a,b数组当前元素，将小的元素放前面，下标后移
    {
        if(a[i]<=b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while(i<n1)      //将剩余元素拷贝过去
    {
        c[k++] = a[i++];
    }
    while(j<n2)
    {
        c[k++] = b[j++];
    }
    return c;
}

 2.删除数组中重复元素

void delete_same(int a[],int &n)
{
    int i,j;
    if(n==0)
        return;
    else
    {
        for(i = 0,j = 1;j<n;j++)
        {
            if(a[i]<a[j])
                a[++i] = a[j];
        }
    }
    n = i+1;
}

3.已知一个数组A，要求将数组元素循环左移p位。如一个数组A{a1,a2,a3,a4,a5}循环左移3位变成A{a4,a5,a1,a2,a3}. 一个思路是利用辅助数组，时间复杂度为O(n),空间复杂度为O(p)。还有一种高效的策略是将A的前P个元素逆置，再将后n-p个元素逆置，最后逆置整个数组。时间复杂度为O(n),空间复杂度为O(1)

void reverseA(int a[],int b,int e) //将b-e之间的数组逆序
{
    int mid = (b+e)/2;
    for(int i = b;i < mid;i++)
    {
        int t = a[i];
        a[i] = a[e-(i-b)];
        a[e-(i-b)] = t;
    }
}

void moveA(int a[],int n,int p)
{
    reverseA(a, 0, p-1);
    reverseA(a, p, n-1);
    reverseA(a, 0, n-1);
}

4.两个有序序列，查找这两个有序序列的中位数。

 

int findmid(int a[],int b[],int n)
{
    int s1 = 0,e1 = n-1;
    int s2 = 0,e2 = n-1;
    while(s1 != e1&&s2 != e2){
        int m1 = (s1+e1)/2;
        int m2 = (s2+e2)/2;
        if(a[m1]==b[m2])
            return a[m1];
        else if(a[m1]<b[m2]){
            if((s1+d1)%2==0)
            {
                s1 = m1;
                e2 = m2;
            }
            else
            {
                s1 = m1+1;
                e2 = m2;
            }
        }
        else
        {
            if((s2+d2)%2==0)
            {
                e1 = m1;
                s2 = m2;
            }
            else
            {
                e1 = m1;
                s2 = m2+1;
            }
        }
    }
    return a[s1]<b[s2]?a[s1]:b[s2];
}

 


联系
我们