正文

【原创】两个有序数组相关的算法2010-03-17 23:09:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/edwardguo/50796.html

分享到:

1、将两个有序数组合并为一个有序数组

int[] MergeArray(int[] arrayX, int[] arrayY)
{
    int arrayXCount = arrayX.Count;
    int arrayYCount = arrayY.Count;
    int totalCount = arrayXCount + arrayYCount;
    int[] mergedArray = new int[totalCount];
    int i=0,j=0;
    while((i!=arrayXCount)&&(j!=arrayYCount))
    {
        if(arrayX[i] <= arrayY[j])
        {
            mergedArray[i+j] = arrayX[i];
            i++;               
        }
        else
        {
            mergedArray[i+j] = arrayY[j];
            j++;
        }
    }
}

2、找出两个排好序的数组中的不同数据,要求最优算法

List<int> MergeArray(int[] arrayX, int[] arrayY)
{
    int arrayXCount = arrayX.Count;
    int arrayYCount = arrayY.Count;
    int i=0,j=0;
    List<int> resultArray = new List<int>();
    while((i!=arrayXCount)&&(j!=arrayYCount))
    {
        if(arrayX[i] < arrayY[j])
        {
            resultArray.Add(arrayX[i]);
            i++;
        }
        else if (arrayX[i] > arrayY[j])
        {
            resultArray.Add(arrayY[j]);
            j++;
        }
        else
        {
            i++;
            j++;  
        }
    }
    return resultArray;
}

 

3、 两个有序数组A,B,查出只在a中有的数。 要求时间复杂度为 Om+n);

List<int> GetUniqueArrayA(int[] arrayX, int[] arrayY)
{
    int arrayXCount = arrayX.Count;
    int arrayYCount = arrayY.Count;
    int i=0,j=0;
    List<int> resultArray = new List<int>();
    while((i!=arrayXCount)&&(j!=arrayYCount))
    {
        if(arrayX[i] < arrayY[j])
        {
            resultArray.Add(arrayX[i]);
            i++;
        }
        else if (arrayX[i] > arrayY[j])
        {
            j++;
        }
        else
        {
            i++;
            j++;  
        }
    }
    return resultArray;
}

 

阅读(6315) | 评论(5)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册