Gabungkan dua daftar yang diurutkan

14

Gabungkan Sortir

Dalam tantangan ini, Anda akan menerapkan subrutin gabungan dari semacam gabungan. Khususnya, Anda harus membuat fungsi atau program atau kata kerja atau serupa yang mengambil dua daftar, masing-masing diurutkan dalam urutan meningkat, dan menggabungkannya ke dalam satu daftar diurutkan dalam urutan meningkat. Persyaratan:

- Algoritme Anda harus mengambil jumlah waktu linear asimtotik dalam ukuran input. Tolong berhenti memberikan solusi O (n ^ 2).

  • Anda tidak boleh menggunakan fungsi bawaan yang mampu mengurutkan daftar, atau menggabungkan daftar, atau hal-hal seperti itu. Kebijaksanaan penulis.
  • Kode harus dapat menangani elemen berulang.
  • Jangan khawatir tentang daftar kosong.

Contoh:

merge([1],[0,2,3,4])
[0,1,2,3,4]

merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]

Ini , jadi semoga kode terpendek menang!

isaacg
sumber
Apakah kita harus menangani elemen berulang dalam daftar, atau hanya di antara kedua daftar?
Keith Randall
Katakanlah keduanya. Idenya adalah bahwa Anda harus dapat menggunakan ini untuk melakukan semacam penggabungan.
isaacg
Apakah halal untuk mengalahkan array input?
skibrianski
3
Saya tidak yakin bagaimana menafsirkan algoritma harus mengambil jumlah waktu linear asimptot . Algoritma tidak membutuhkan waktu, implementasi lakukan. Waktu eksekusi jawaban Golfscript saya adalah O (menakutkan) dengan interpreter Ruby, tetapi Tester Golfscript Online berperilaku jauh lebih baik dan sebenarnya bisa linear (tidak ada cara nyata mengatakan tanpa kode sumber sekalipun). Maksud saya adalah: b=a;b=b.lengthdapat menduplikasi seluruh array a(dan menghasilkan waktu O (n ^ 2) jika dieksekusi untuk setiap elemen) atau menduplikat hanya referensi ke array (O (n) waktu). Yang mana yang diperhitungkan?
Dennis
1
Saya kira dalam kasus-kasus seperti ini, lakukan yang terbaik untuk mengetahuinya, tetapi jika Anda benar-benar tidak tahu, Anda dapat menganggap semuanya berjalan baik, seperti alternatif kedua yang Anda sebutkan. Anda dapat menganggap bahwa juru bahasa berfungsi dengan baik jika bahasa Anda tidak memiliki juru bahasa standar.
isaacg

Jawaban:

8

Rebmu ( 35 32 karakter)

u[iG^aNXa[rvA]apGtkFaM?fA]apGscA

Uji

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[1 5 10 17 19] [2 5 9 11 13 20]] 
== [1 2 5 5 9 10 11 13 17 19 20]

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[2 5 9 11 13 20] [1 5 10 17 19]] 
== [1 2 5 5 9 10 11 13 17 19 20]

Tentang

Rebmu adalah dialek Rebol yang memungkinkan 'meremas' kode reguler untuk situasi yang membutuhkan keringkasan. Tanpa basa-basi, kode ini bekerja seperti:

u [                     ; until
    i g^ a nx a [       ; if greater? args next args
       rv a             ; reverse args
    ]                   ; (we want the block containing the next value first)

    ap g tk f a         ; append output take first args
    m? f a              ; empty? first args
]                       ; (first block is now empty)

ap g sc a               ; append output second args
                        ; (add the remainder of the second)

Saya percaya ini memenuhi persyaratan O (n) karena blok sampai paling banyak dilingkarkan sebanyak panjang input (dan reversehanya mengganti urutan wadah blok input, bukan blok itu sendiri). Menggunakan takemungkin adalah kebebasan, tetapi masih merupakan efisiensi kecil.

Rebol ( 83 75 karakter)

Hanya sedikit berbeda: di Rebol, path adalah ekspresi yang lebih pendek dari firstatau second. aadalah blok input yang berisi dua blok:

until[if a/2/1 < a/1/1[reverse a]append o:[]take a/1 tail? a/1]append o a/2
rgchris
sumber
5

Solusi OP:

Haskell 49 44 40

k@(p:r)%l@(q:s)|p>=q=q:k%s|0<1=l%k
a%_=a

Python 131 105 101 99 93

Dengan terima kasih kepada @Evpok:

f=lambda u,v:v and(v[-1]<u[-1]and f(v,u)or[b.append(a)for a,b in[(v.pop(),f(u,v))]]and b)or u
isaacg
sumber
1
Anda dapat menulis a%b=a++bsetelah pencocokan pola utama untuk menangani daftar kosong, yang akan memangkas beberapa karakter.
desir
Bukankah solusi Haskell gagal jika daftar pertama kehabisan konten?
John Dvorak
Jika Anda melihat fungsi pertama, itu secara rekursif memanggil fungsi dengan daftar singkat sebagai argumen kedua, dan daftar panjang sebagai argumen pertama, atau menukar argumen. Oleh karena itu, argumen pertama tidak pernah menjadi pendek. Karena dengan OP itu tidak mulai kosong, tidak akan pernah kosong.
isaacg
4

Python (79)

from itertools import*
def m(*a):
 while any(a):yield min(compress(a,a)).pop(0)

Python (95, jika kita tidak diizinkan untuk mengembalikan generator)

from itertools import*
def m(*a):
 r=[]
 while any(a):r+=[min(compress(a,a)).pop(0)]
 return r

Itertools adalah solusi untuk semua masalah duniawi.

Bonus: keduanya bekerja berdasarkan jumlah daftar yang berubah-ubah, dan LAKUKAN khawatir tentang daftar kosong (seperti, mereka akan dengan senang hati mengambil 2 daftar kosong, dan mengembalikan daftar kosong, atau mengambil 1 daftar kosong dan 1 daftar tidak kosong, dan mereka akan mengembalikan yang tidak kosong. Fitur tambahan lain dari 2 yang tidak menghasilkan: mereka juga akan berjalan tanpa argumen, dan hanya mengembalikan daftar kosong.)

Tidak Disatukan:

from itertools import *  # Import all items from itertools
def m(*a):               # Define the function m, that takes any number of arguments, 
                         #  and stores those arguments in list a
    r=[]                 # Create an empty list r                         
    while any(a):        # While any element in a returns True as value:
        b=compress(a,a)  # Remove any element from a that isn't True (empty lists)
                         #  The example in the official documentation is this one:
                         #  compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
        c=min(b)         # Sort the lists by first value, and take the first one of these.
        d=c.pop(0)       # Take the first element from c
        r.append(d)      # Append this first element to r
    return r             # Gives back r
ɐɔıʇǝɥʇu
sumber
Dalam solusi Anda tanpa generator, gunakan r+=[...]sebagai gantinya r.append(...)(hemat 4 karakter setiap kali)
hlt
Saya tidak bermaksud menyinggung apa pun, tetapi jika jawaban Anda berisi kode dalam bahasa yang hanyalah bahasa lain dengan modifikasi yang dibuat khusus untuk bermain golf, saya akan menurunkannya. Sayang sekali, jawaban python yang sebenarnya baik.
undergroundmonorail
Jika Anda membaginya menjadi beberapa posting yang berbeda, saya akan menambahkan yang python.
undergroundmonorail
4
@undergroundmonorail Apakah Anda membatalkan semua jawaban GolfScript?
Evpok
1
@Evpok Sekarang Anda menyebutkannya, mungkin juga melemparkannya pada meta, dan lihat apa yang mereka katakan di sana.
ɐɔıʇǝɥʇuʎ
3

C - 75

Ini beroperasi pada NULLarray yang diakhiri int *, meskipun itu akan bekerja sama baiknya untuk pointer ke tipe lain dengan mengganti fungsi perbandingan yang sesuai untuk **b < **a(misalnya, strcmp(*b, *a) < 0).

void m(int**a,int**b,int**c){while(*a||*b)*c++=!*a||*b&&**b<**a?*b++:*a++;}

Tidak Disatukan:

void merge(int **a, int **b, int **c)
{
    while(*a || *b)
        *c++ = !*a || *b && **b < **a
            ? *b++
            : *a++;
}
laindir
sumber
3

Golfscript, 29 27 30 29 26 byte

~{[email protected]=@<{}{\}if(@@.}do;~]p

atau

~{[email protected]=@>{\}*(@@.}do;~]p

Bagaimana itu bekerja

Perintah

golfscript merge.gs <<< '[2 3] [1 4]'

akan diproses sebagai berikut:

~            # Interpret the input string.
             #
             # STACK: [2 3] [1 4]
{            #
    .@=0.@=0 # Duplicate the two topmost arrays of the stack and extract their first 
             # elements. This reverses the original order of the first copy.
             #
             # STACK: [1 4] [2 3] 2 1
             #
    >        # Check if the respective first elements of the arrays are ordered.
             #
             # STACK: [1 4] [2 3] 1
             #
    {\}*     # If they are not, swap the arrays. This brings the array with the smallest
             # element to the top of the stack.
             #
             # STACK: [2 3] [1 4]
             #
    (@@      # Shift the first element of the array on top of the stack and rotate it
             # behind the arrays.
             #
             # STACK: 1 [2 3] [4]
             #
    .        # Duplicate the topmost array.
             #
             # STACK: 1 [2 3] [4] [4]
             #
}do          # Repeat this process if the array is non-empty.
             #
             # STACK: 1 [2 3] [4] -> 1 2 [4] [3] -> 1 2 3 [4] []
             #
;~           # Delete the empty array from the stack and dump the non-empty array.
             #
             # STACK: 1 2 3 4
             #
]p           # Combine all elements on the stack into a single array, the to a string and
             # print.

Outputnya adalah:

[1 2 3 4]
Dennis
sumber
Apakah duplikasi array dalam stack membuatnya O (n ^ 2)?
desir
@swish: Saya bukan ilmuwan komputer, tapi saya akan mengatakan itu tergantung pada implementasinya. Jika penerjemah benar-benar menduplikasi seluruh array, saya kira itu benar.
Dennis
Versi sebelumnya adalah O (n ^ 2) untuk array yang sangat mirip (misalnya, [1 1 1 ... 2]dan [1 1 1 ... 3]), karena membandingkan array (daripada elemen pertama mereka) akan sangat lambat dalam kasus ini.
Dennis
Satu-satunya operasi array yang terjadi di versi baru adalah duplikasi, swapping, dan rotasi pada stack. Karena array duplikat hanya digunakan untuk mengekstraksi elemen tunggal dan menguji array untuk kekosongan (keduanya operasi destruktif dalam Golfscript), kode di atas dapat dijalankan dalam waktu O (n) waktu (dengan menduplikasi, menukar dan memutar referensi ke array). Kinerja aktual tergantung pada penerjemah.
Dennis
2

J - 42 33

Versi modifikasi dari sini + komentar dari @algorithmshark

k=:(m}.),~0{]
m=:k~`k@.(>&{.) ::,

kmenambahkan kepala array kanan ke ekor gabungan dari kedua array. k~sama, tetapi dengan array terbalik. (>&{.)membandingkan kepala. Kode akan memunculkan kesalahan jika salah satu array kosong, dalam hal ini kami mengembalikan hanya gabungan mereka ,.

desir
sumber
Saya menduga bahwa karena /:~ a,badalah jawaban terlarang (bersama [:/:~,), bahwa Anda memotret untuk jawaban terpendek yang tidak termasuk /:, kan?
Dane
Saya akan menunjukkan bahwa pertanyaannya menyatakan, "Jangan khawatir tentang daftar kosong."
Dane
@Dane Tes untuk kekosongan yang diperlukan agar rekursi berhenti.
desir
m=:k~`k@.(>&{.)`,@.(0=*&#)menghemat 2 char.
algorithmshark
Bahkan, Anda bisa mendapatkan semuanya menjadi 33 char: k=:(m}.),~0{]and m=:k~`k@.(>&{.) ::,. Kami menggunakan 0{untuk melempar kesalahan ketika daftar kosong, dan kemudian menangkap kesalahan itu dan keluar bersama ,.
algorithmshark
2

JavaScript (ES6), 69 79 byte

f=(a,b,c=[])=>(x=a[0]<b[0]?a:b).length?f(a,b,c.concat(x.shift())):c.concat(a,b)

Bagaimana itu bekerja

f = (a, b, c = []) =>          // `f' is a function that takes arguments `a', `b' and `c' -
                               // `c' defaults to `[]' - which returns the following
                               // expression:
                               //
 (x = a[0] < b[0] ? a : b)     // Store the array among `a' and `b' with the smaller first 
                               // element in `x'.
                               //
 .length ?                     // If it's non-empty,
                               //
  f(a, b, c.concat(x.shift())) // append the first element of array `x' to array `c' and run
                               // `f' again;
                               //
  : c.concat(a,b)              // otherwise, append the arrays `a' and `b' to `c'.
                               //
)
Dennis
sumber
Membandingkan array dengan <operator tidak valid karena melakukan perbandingan string:f([123, 456, 789], [1, 2, 3, 4, 5]) => [1, 123, 2, 3, 4, 456, 5, 789]
nderscore
@nderscore: Benar. Itu tidak akan berhasil, karena membandingkan seluruh array mungkin bukan O (n). Hal yang sama tampaknya berlaku untuk tes non-kekosongan, yang harus mengubah seluruh array menjadi string.
Dennis
Ya, saya tidak yakin apa yang besar untuk konversi tipe string array->.
nderscore
1
Menggabungkan sebuah array dengan []dan kemudian mengubahnya menjadi string membutuhkan O (n) waktu. Melakukannya sekali untuk semua elemen n dari array membutuhkan O (n ^ 2) waktu.
Dennis
Masuk akal. Mengerti.
nderscore
2

Python (63) (69) (71)

def m(a,b):
 if a[0]>b[0]:a,b=b,a
 return[a.pop(0)]+(m(a,b)if a else b)

Saya menulis ini sebelum melihat komentar OP pada runtimes dari jawaban lain, jadi ini adalah solusi lain yang O (n) dalam algoritma tetapi tidak implementasi.

Tidak
sumber
Algoritma apa yang diekstrak dari depan array sebagai O (1)? Algoritme apa yang membuat perbandingan daftar dengan O (1)? Juga, Anda bisa bermain golf lebih jauh dengan mengubah ... jika ... yang lain ... menjadi ... dan ... atau ...
isaacg
@isaacg Tembak, saya lupa tentang pengulangan yang mungkin membuat daftar perbandingan O (n). Jadi, saya telah melakukan optimasi untuk 6 karakter lainnya. Anda dapat mengekstrak dari dan menambahkan ke depan di O (1) dalam daftar tertaut. Saya tidak melihat bagaimana Anda dapat membuat ... dan ... atau ... bermain bagus dengan mengembalikan nilai.
xnor
OK, saya mengerti sekarang bagaimana melakukan ... dan ... atau ..., tetapi itu tidak menghemat karakter karena diperlukan parens. return[a.pop(0)]+(a and m(a,b)or b)
xnor
@isaacg: Untuk mengekstrak bagian depan array di O (1), cukup tambahkan pointer pointer sehingga menunjuk ke elemen kedua dan lepaskan memori yang dikonsumsi oleh elemen pertama.
Wrzlprmft
@Wrzlprmft Saya tidak bisa mendapatkan trik array untuk bekerja karena kedua elemen array dievaluasi terlepas dari nilai boolean, yang melempar kesalahan ketika a adalah daftar kosong. Apakah ada cara singkat untuk membuat "array malas"?
xnor
2

Haskell, 35 byte

a#b@(c:d)|a<[c]=b#a|0<1=c:a#d
a#_=a

Haskell, 30 byte (tidak bersaing)

Versi yang tidak bersaing ini hanya menjamin runtime linier jika adan bmemiliki elemen yang terpisah; selain itu masih berjalan dengan benar tetapi dapat menggunakan waktu kuadratik.

a#b|a<b=b#a|c:d<-b=c:a#d
a#_=a
Anders Kaseorg
sumber
2

PHP 91 98 91 byte

sunting # 1: Kosong $bmembutuhkan kondisi tambahan di kurung kurawal (+7).
sunting # 2: pegolf minor
sunting # 3: menambahkan versi kedua

cukup lurus ke depan. Bagian terbaik adalah ternary di dalam array_shift
(yang gagal jika Anda mencobanya tanpa keriting)

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a&(!$b|$a[0]<$b[0])?a:b});return$c;}

atau

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a?!$b|$a[0]<$b[0]?a:b:b});return$c;}

ungolfed

function m($a,$b)
{
    $c=[];
    while($a||$b)
    {
        $c[] = array_shift(${
            $a&&(!$b||$a[0]<$b[0])
                ?a
                :b
        });
#       echo '<br>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    }
    return $c;
}

uji

$cases = array (
    [1],[0,2,3,4], [0,1,2,3,4],
    [1,5,10,17,19],[2,5,9,11,13,20], [1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20],
    [1,2,3],[], [1,2,3],
    [],[4,5,6], [4,5,6],
);
function outA($a) { return '['. implode(',',$a). ']'; }
echo '<table border=1><tr><th>A</th><th>B</th><th>expected</th><th>actual result</th></tr>';
while ($cases)
{
    $a = array_shift($cases);
    $b = array_shift($cases);
#   echo '<hr>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    $expect = array_shift($cases);
    $result=m($a,$b);
    echo '<tr><td>',outA($a),'</td><td>',outA($b),'</td><td>', outA($expect), '</td><td>', outA($result),'</td></tr>';
}
echo '</table>';
Titus
sumber
Saya tidak bisa mengerti mengapa Anda membuatnya tidak sederhana, $a&(!$b|$a[0]<$b[0])?$a:$bbukan${$a&(!$b|$a[0]<$b[0])?a:b}
Jörg Hülsermann
1
@ JörgHülsermann array_shiftParameter digunakan oleh referensi. Itu harus menjadi variabel; sebuah ekspresi tidak akan berhasil.
Titus
1

Ayo, 124 karakter

func m(a,b[]int)(r[]int){for len(a)>0{if len(b)==0||a[0]>b[0]{a,b=b,a}else{r=append(r,a[0]);a=a[1:]}};return append(r,b...)}
Keith Randall
sumber
1

JavaScript - 133

function m(a,b){c=[];for(i=j=0;i<a.length&j<b.length;)c.push(a[i]<b[j]?a[i++]:b[j++]);return c.concat(a.slice(i)).concat(b.slice(j))}

Jenis pendekatan yang sama dengan OP.

Mat
sumber
1

perl, 87 karakter / perl 5.14, 78 + 1 = 79 karakter

Implementasi ini mengganggu referensi array input. Selain itu, itu sangat mudah: sementara kedua array memiliki sesuatu, bergeser ke bawah dari keduanya. Kemudian kembalikan bit yang digabungkan bergabung dengan bit yang tersisa (hanya satu dari @ $ x atau @ $ y akan tetap). Perl5 langsung, 87 karakter:

sub M{($x,$y,@o)=@_;push@o,$$x[0]>$$y[0]?shift@$y:shift@$x while@$x&&@$y;@o,@$x,@$y}

Menggunakan perl 5.14.0 dan pergeseran arrayref yang baru: 78 karakter + 1 penalti char = 79 karakter:

sub M{($x,$y,@o)=@_;push@o,shift($$x[0]>$$y[0]?$y:$x)while@$x&&@$y;@o,@$x,@$y}
skibrianski
sumber
*bukannya &&akan menghemat satu byte. Dan bahkan lebih jikasub M{map{shift(!@$x+@$y*($$y[0]<$$x[0])?$y:$x)}map@$_,($x,$y)=@_}
user2846289
@ Sadim, wow. kerja bagus. Silakan dan posting itu jika Anda mau - Saya tidak akan pernah berpikir untuk melakukan trik peta ganda daripada mendorong pada array.
skibrianski
1

Jawa: 144

Ini sangat mudah. Fungsi yang mengambil dua array dan mengembalikan satu, versi gabungan, golf dan tanpa pembungkus kompilasi:

int[]m(int[]a,int[]b){int A=a.length,B=b.length,i,j;int[]c=new int[A+B];for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);return c;}

Tidak disatukan (dengan pembungkus yang dapat dikompilasi dan dapat dijalankan):

class M{
    public static void main(String[]args){
        int[]a=new int[args[0].split(",").length];
        int i=0;
        for(String arg:args[0].split(","))
            a[i++]=Integer.valueOf(arg);
        int[]b=new int[args[1].split(",").length];
        int j=0;
        for(String arg:args[1].split(","))
            b[j++]=Integer.valueOf(arg);
        int[]c=(new M()).m(a,b);
        for(int d:c)
            System.out.printf(" %d",d);
        System.out.println();
    }
    int[]m(int[]a,int[]b){
        int A=a.length,B=b.length,i,j;
        int[]c=new int[A+B];
        for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);
        return c;
    }
}

Contoh eksekusi:

$ javac M.java
$ java M 10,11,12 0,1,2,20,30
 0 1 2 10 11 12 20 30
$ java M 10,11,12,25,26 0,1,2,20,30
 0 1 2 10 11 12 20 25 26 30

Setiap tips untuk dipersingkat akan dihargai.

ProgrammerDan
sumber
1

Scala, 97 byte

Solusi rekursif dengan O (n). Untuk mempersingkat kode, terkadang operasi dilakukan dengan mengganti 2 parameter yang dapat dipertukarkan, yaitu f (a, b) panggilan f (b, a).

type L=List[Int];def f(a:L,b:L):L=if(a==Nil)b else if(a(0)<=b(0))a(0)::f(a.drop(1),b) else f(b,a)

Tidak Disatukan:

type L=List[Int]

def f(a:L, b:L) : L =
  if (a == Nil)
    b 
  else 
    if (a(0) <= b(0))
      a(0) :: f(a.drop(1), b) 
    else
      f(b,a)
lambruscoAcido
sumber
Pengecualian jika a tidak kosong, tetapi b kosong
Dan Osipov
1

APL (32)

{⍺⍵∊⍨⊂⍬:⍺,⍵⋄g[⍋g←⊃¨⍺⍵],⊃∇/1↓¨⍺⍵}

Penjelasan:

{⍺⍵∊⍨⊂⍬                               if one or both of the arrays are empty
        :⍺,⍵                           then return the concatenation of the arrays
             ⋄g[⍋g←⊃¨⍺⍵]              otherwise return the sorted first elements of both arrays
                          ,⊃∇/        followed by the result of running the function with
                               1↓¨⍺⍵}  both arrays minus their first element
marinus
sumber
1

LISP, 117 byte

Algoritma berakhir dengan n + 1iterasi, di mana nadalah panjang daftar input terpendek.

(defun o(a b)(let((c(car a))(d(car b)))(if(null a)b(if(null b)a(if(< c d)(cons c(o(cdr a)b))(cons d(o a(cdr b))))))))
PieCot
sumber
0

PYG (50)

def m(*a):
 while An(a):yield Mn(ItCo(a,a)).pop(0)

PYG (64, sekali lagi, jika tidak ada generator yang diizinkan.):

def m(*a):
 r=[]
 while An(a):r+=[(Mn(ItCo(a,a)).pop(0)]
 return r

Adaptasi jawaban Python saya .

ɐɔıʇǝɥʇu
sumber
0

Python - 69 byte

def m(A,B):
    C=[]
    while A and B:C+=[[A,B][A>B].pop(0)]
    return C+A+B

Jika urutan input dan output menurun, ini bisa disingkat menjadi 61 byte :

def m(A,B):
    C=[]
    while A+B:C+=[[A,B][A<B].pop(0)]
    return C

Dan lebih jauh ke 45 byte jika generator diizinkan:

def m(A,B):
    while A+B:yield[A,B][A<B].pop(0)
Wrzlprmft
sumber
Ini jelas bukan O (n). .pop (0) dan + = keduanya O (n) operasi yang Anda lakukan O (n) kali.
isaacg
Saya bahkan tidak tahu sampai sekarang bahwa daftar tidak diimplementasikan sebagai daftar dalam Python dan bahkan kemudian pop(0)dapat diimplementasikan dalam O (1) dan +=setidaknya dapat diimplementasikan lebih baik daripada O (n) (lihat tautan). Omong-omong, solusi Anda menggunakan +=(yaitu, appenddan extend) sesering milik saya. Lagi pula, semua itu adalah pertanyaan implementasi (sejauh yang saya tahu), jadi dalam implementasi Python (fiktif), di mana daftar diimplementasikan sebagai daftar, fungsi saya adalah O (n). Akhirnya pertanyaan Anda membutuhkan algoritme menjadi O (n), dan pertanyaan saya adalah.
Wrzlprmft
Sebenarnya, append dan extended diimplementasikan secara berbeda dalam python daripada + =. + = membuat daftar baru, sementara .append dan .extend modifikasi yang sudah ada.
isaacg
0

Perl 6: 53 karakter

sub M(\a,\b){{shift a[0]>b[0]??b!!a}...{a^b},a[],b[]}

Bergeser dari mana saja dari aatau bmemiliki nilai lebih kecil, hingga aXOR b(a^b ) benar. Lalu kembalikan apa pun yang tersisa, ratakan ( []) array ke dalam daftar ( a[],b[]).

Dengan asumsi pergeseran dari awal array adalah O (n), kasus terburuk adalah dua perbandingan dan satu shift per elemen, sehingga algoritmenya adalah O (n).

Mouq
sumber
0

JavaScript (ES5) 90 86 90 byte

function f(a,b){for(o=[];(x=a[0]<b[0]?a:b).length;)o.push(x.shift());return o.concat(a,b)}

sunting: (90 -> 86) Memindahkan terner ke dalam untuk kondisi loop. Ide yang dicuri dari Dennis.

sunting: (86 -> 90) Array yang dihapus ke String cast, karena melanggar persyaratan O (n) .

nderscore
sumber
0

Mathematica, 137 135

m[a_,b_]:=(l=a;Do[Do[If[b[[f]]<=l[[s]],(l=Insert[l,b[[f]],s];Break[]),If[s==Length@l,l=l~Append~b[[f]]]],{s,Length@l}],{f,Length@b}];l)

Memasukkan:

m[{2,2,4,6,7,11},{1,2,3,3,3,3,7}]

Keluaran:

{1, 2, 2, 2, 3, 3, 3, 3, 4, 6, 7, 7, 11}

Tidak Disatukan:

mergeList[a_, b_] := (
    list = a;
    Do[
        Do[(
            If[
                b[[f]] <= list[[s]],
                (list = Insert[list, b[[f]], s]; Break[]),
                If[
                    s == Length@list,
                    list = list~Append~b[[f]]
                ]
        ]),
        {s, Length@list}
    ],
    {f, Length@b}
    ];
    list
)

Mungkin bisa berbuat lebih baik.

kukac67
sumber
m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b;
alephalpha
0

R, 80

Solusi yang sama seperti di Scala dan bahasa lainnya. Saya tidak begitu yakin tentang x [-1] adalah O (1).

f=function(a,b)if(length(a)){if(a[1]<=b[1])c(a[1],f(a[-1],b))else f(b,a)}else b
lambruscoAcido
sumber
0

Mathematica, 104 byte

Reap[{m,n}=Length/@{##};i=k=1;Do[If[k>n||TrueQ[#[[i]]<#2[[k]]],Sow@#[[i++]],Sow@#2[[k++]]],n+m]][[2,1]]&

Fungsi anonim, menyimpan panjang dua daftar input dalam variabel mdan n, kemudian setiap iterasi dariDo loop Sowmerupakan elemen dari satu daftar yang menambah penghitung untuk daftar itu ( iuntuk yang pertama, kuntuk yang kedua) dengan satu. Jika salah satu penghitung melebihi panjang daftar, Ifpernyataan akan selaluSow elemen dari daftar lainnya. Setelah n+moperasi, semua elemen telah diurus. Reapatau lebih tepatnya bagian [[2,1]]dari outputnya adalah daftar elemen-elemen sesuai urutannya Sown.

Saya tidak yakin dengan internal (mengakses bagian daftar O(1)operasi atau tidak), tetapi pengaturan waktu tampak cukup linier pada mesin saya sehubungan dengan panjang daftar input.

LLlAMnYP
sumber