一道算法题

问题,有两个有序int数组A,B,长度均为k,
求一个新有序数组C,C中元素为A中取一个元素与B中取一个元素的和~
比如
a = {1, 2, 3, 4, 5, 6, 7};
b = {1, 2, 3, 4, 5, 6, 7};

结果为
1+1=2
1+2=3
2+1=3
1+3=4
2+2=4
1+4=5
2+3=5

我的解题思路

设置一组指针数组pointA ,表示A值和B组合以后的位置

pointA[0]=0表示指向a1 b1的点
pointA[3]=4表示指向a4 b5的点
pointA[4]=-1表示a5和任意b的组合都不用考虑

指针不断向下向右走,判断所有指针上点,取个和最小的就是结果

A
^  指针  1   2   3   4   5   6   7  > B
1   0   2   3
2   0   3
3  -1
4  -1
5  -1
6  -1
7  -1

下面附带上我写的代码

/**
 * Created with IntelliJ IDEA.
 * User: SunDP
 * Date: 12-11-6
 * Time: 下午10:44
 * To change this template use File | Settings | File Templates.
 */
public class Sort {

    static int pointRound = 2;

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 5, 7 , 9, 11,15,24,99};
        int[] b = {2, 3, 6, 8, 10, 11,13,17,19,20};
        int[] result = new int[a.length];
        int[] pointA = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            pointA[i] = -1;
        }
        pointA[0] = 0;
        pointA[1] = 0;

        for (int i = 0; i < a.length; i++) {
            compare(pointA, a, b, result, i, pointRound);
        }
    }

    public static void compare(int[] pointA, int[] a, int[] b, int[] result, int round, int tempPointRound) {
        int temp = 10000000;
        int tempPoint = 0;
        for (int i = 0; i < tempPointRound; i++) {
            if (pointA[i] != -1) {
                if (a[i] + b[pointA[i]] < temp) {
                    temp = a[i] + b[pointA[i]];
                    tempPoint = i;
                }
            }
        }
        result[round] = a[tempPoint] + b[pointA[tempPoint]];
        System.out.println(a[tempPoint] + "+" + b[pointA[tempPoint]] + "=" + result[round]);
        if (pointA[tempPoint] == 0 && tempPoint < pointA.length - 1) {
            pointA[tempPoint + 1] = 0;
            pointRound = tempPointRound+1;
        }
        if (pointA[tempPoint] < a.length - 1) {
            pointA[tempPoint]++;
        } else {
            pointA[tempPoint] = -1;
        }
    }
}

这个时间复杂度是k平方,貌似又不是k平方,求高人帮计算~

后续:没事的时候思考了一下,把他想象成一个汉诺塔,塔的编号分别是b0,b1,b2….横竖都是有序的,所以左下角的点一定是最小值,

a6 a6 a6 a6 a6 a6 a6
a5 a5 a5 a5 a5 a5 a5
a4 a4 a4 a4 a4 a4 a4
a3 a3 a3 a3 a3 a3 a3
a2 a2 a2 a2 a2 a2 a2
a1 a1 a1 a1 a1 a1 a1
a0 a0 a0 a0 a0 a0 a0
------------------------------
b0 b1 b2 b3 b4 b5 b6

最小值为a0+b0,将这个值取出,此时计算所有柱子上最底下元素的值,
即a1+b0,a0+b1,a0+b2,a0+b3,a0+b4,a0+b5,a0+b6
此时a0+b1,a0+b2,a0+b3,a0+b4,a0+b5,a0+b6一定是有序的,这时,我们可以看成把a1+b0进行插入排序

a6 a6 a6 a6 a6 a6 a6
a5 a5 a5 a5 a5 a5 a5
a4 a4 a4 a4 a4 a4 a4
a3 a3 a3 a3 a3 a3 a3
a2 a2 a2 a2 a2 a2 a2
a1 a1 a1 a1 a1 a1 a1
a0 a0 a0      a0 a0 a0
——————————
b1 b2 b3 b0 b4 b5 b6

(假设b0+a1的位置在b3+a0和b4+a0之间)

那么此时最小值一定是 a0+b1,在b1中取出a0,再次进行排序,不断执行,直到n次。

算法分析:折半查找时间复杂度是log(n),共要执行n次,所以该算法的时间复杂度是n*log(n)

 

 

 

 

Question 1:

为什么折半查找时间复杂度是log(n):

Answer:

假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道:
如果n = 1,则t(n) = c1
如果n > 1,则t(n) = t(n/2) + c2
其中n/2需要取整,c1、c2都是常数

对于正整数n,可以有:
t(n) = t(n/2) + c2
= t(n/4) + 2*c2
= t(n/8) + 4*c2
= …
= t(n/(2的k次方)) + k*c2
一直推演下去,直到n/(2的k次方)等于1,也就是k = log2(n),此时等式变为:
t(n) = t(1) + k*c2
= c1 + log2(n)*c2

于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度,因为它们之间仅仅差了一个常量系数而已。

这个是不严格的推导,因为没有考虑整数除以2之后可能有余数的情况。但即使有余数,也是不影响时间复杂度的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注