Соединить два списка, используя условие

Question

мне нужно сцепить списки A и B используя условие, что два списка преобразования в список C, с одной и той же длины, но каждый i элемент не меняет позицию и список сортируется. Иначе вернуть пустой список:

A = ['a', 'b', 'c'] 
B = ['x', 'y', 'z'] 

сцепленных к: C = ['a', 'b', 'z'].

или

A = ['8', '2', '3'] 
B = ['1', '2', '0'] 

сцепленных к: C = ['1', '2', '3'].

Я абсолютно не знаю, как я могу начать решать свою проблему. Какой алгоритм я должен использовать?

UPD:

Еще примеры:

A = ['a', 'b', 'c'] 
B = ['x', 'x', 'x'] 

результатом является: ['a', 'b', 'x']

A = ['b', 'a'] 
B = ['x', 'c'] 

результат должен быть: ['b', 'c'].

И результат конкатенации этих двух списков является пустой список:

A = ['e','a'], 
B = ['f','b'] 

Answer 1

вам просто нужно переключить последние два элемента в каждом списке ли? Если это так, это простой способ, позволяющий увидеть, что происходит.

lst1 = ['a', 'b', 'c'] 
lst2 = ['x', 'x', 'x'] 

lst3 = lst1 
lst3[len(lst2)-1] = lst2[len(lst2)-1] 

lst3 
Out: ['a', 'b', 'x'] 

Else, объясните логику того, что вы пытаетесь сделать немного больше.

Answer 2

Это можно сделать с помощью жадного алгоритма, перебрать оба списка и принять минимальное значение, которое больше, чем предыдущий элемент, который вы сделали.

prev = None 
A = ['a', 'b', 'c'] 
B = ['x', 'x', 'x'] 
n = len(A) 
result = [] 
for i in range(n): 
    mn, mx = A[i],B[i] 
    if mx<mn: 
     mn,mx = mx,mn 
    if prev == None or mn >= prev: 
     prev = mn 
     result.append(prev) 
    elif mx >= prev: 
     prev = mx 
     result.append(prev) 
    else: 
     print "can't be done" 
     break 
if len(result) == n: 
    print result