合并两个有序数组

2013-10-30 10:36  1360人阅读  评论 (0)
Tags: 算法

C

#require <stdio.h>
#define ALEN 12
#define BLEN 16

main() {
    int a[ALEN] = {4,5,8,9,16,18,24,25,35,54,90,98};
    int b[BLEN] = {1,6,7,15,18,18,22,33,45,66,80,83,92,97,99,100};
    int c[ALEN+BLEN] = {};

    int i, j, k;
    for (i = ALEN-1, j = BLEN-1, k = ALEN+BLEN-1; k >= 0; k--) {
        if (i >= 0 && (j < 0 || a[i] > b[j])) {
            c[k] = a[i--];
        } else {
            c[k] = b[j--];
        }
    }

    // int i = 0, j = 0, k = 0;
    // while (i < ALEN && j < BLEN) {
    //  if (a[i] < b[j]) {
    //      c[k++] = a[i++];
    //  } else {
    //      c[k++] = b[j++];
    //  }
    // }
    // while (i < ALEN) {
    //  c[k++] = a[i++];
    // }
    // while (j < BLEN) {
    //  c[k++] = b[j++];
    // }

    int n;
    for (n = 0; n < ALEN+BLEN; n++) {
        printf("%d ", c[n]);
    }
}

Go

package main

import "fmt"

func main() {
    a := []int{4,5,8,9,16,18,24,25,35,54,90,98}
    b := []int{1,6,7,15,18,18,22,33,45,66,80,83,92,97,99,100}
    alen := len(a)
    blen := len(b)
    c := make([]int, alen+blen, alen+blen)

    for i, j, k := alen-1, blen -1, alen+blen-1; k >= 0; k-- {
        if i >= 0 && (j < 0 || a[i] > b[j]) {
            c[k] = a[i]
            i--
        } else {
            c[k] = b[j]
            j--
        }
    }

    fmt.Println(c, alen, blen, len(c))
}

PHP

<?php
$a = array(4,5,8,9,16,18,24,25,35,54,90,98);
$b = array(1,6,7,15,18,18,22,33,45,66,80,83,92,97,99,100);
$alen = count($a);
$blen = count($b);
$c = array_pad(array(), $alen+$blen, null);

for ($i = $alen-1, $j = $blen-1, $k = $alen+$blen-1; $k >= 0; $k--) {
    if ($i >= 0 && ($j < 0 || $a[$i] > $b[$j])) {
        $c[$k] = $a[$i--];
    } else {
        $c[$k] = $b[$j--];
    }
}

echo implode(" ", $c);

Java

class Arr {
    public static void main(String[] args) {
        int[] a = new int[]{4,5,8,9,16,18,24,25,35,54,90,98};
        int[] b = new int[]{1,6,7,15,18,18,22,33,45,66,80,83,92,97,99,100};
        int[] c = new int[a.length+b.length];

        for (int i = a.length-1, j = b.length-1, k = a.length+b.length-1; k >= 0; k--) {
            if (i >=0 && (j < 0 || a[i] > b[j])) {
                c[k] = a[i--];
            } else {
                c[k] = b[j--];
            }
        }

        System.out.println(java.util.Arrays.toString(c));
    }
}

Python

a = [4,5,8,9,16,18,24,25,35,54,90,98]
b = [1,6,7,15,18,18,22,33,45,66,80,83,92,97,99,100]
alen = len(a)
blen = len(b)
c = list(range(alen+blen))

i = alen-1
j = blen-1
k = alen+blen-1
while k >= 0 :
    if i >= 0 and (j < 0 or a[i] > b[j]) :
        c[k] = a[i]
        i -= 1
    else :
        c[k] = b[j]
        j -= 1
    k -= 1

print(c)