1 / 1 / 0
Регистрация: 11.11.2018
Сообщений: 17
1

Объединение двух упорядоченных списков A и B в один упорядоченный список С

22.11.2018, 12:09. Показов 46003. Ответов 10

Помогите, решить, пожалуйста!


Даны два целочисленных списка A и B, упорядоченных по неубыванию. Объедините их в один упорядоченный список С (то есть он должен содержать len(A)+len(B) элементов). Решение оформите в виде функции merge(A, B), возвращающей новый список. Алгоритм должен иметь сложность O(len(A)+len(B)). Модифицировать исходные списки запрещается. Использовать функцию sorted и метод sort запрещается.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.11.2018, 12:09
Ответы с готовыми решениями:

Из двух упорядоченных массивов сформировать один, упорядоченный в обратном направлении
Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N,...

Как из двух списков сделать один список кортежей/списков
Доброго времени суток! Буду очень благодарен, если поможете из двух списков, к примеру a и b,...

Объединение списков в один
Ввести с клавиатуры два списка, содержащих 10 и 5 элементов. Объединить их в один список, включив...

Список: сложение двух списков, их рандомная пересортировка и красивый вывод
Здравствуйте! Огромное спасибо за столь быструю помощь с предыдущим вопросом!...

10
29 / 21 / 8
Регистрация: 23.10.2018
Сообщений: 51
Записей в блоге: 3
22.11.2018, 18:01 2
Предлагаю рассмотреть такой вариант (составляем новый список из min элементов, которые удаляем из списка А+В, если числа повторяются добавляем их столько раз, сколько надо):
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def merger(a, b):
    new_list = []
    d = a + b
    while d:
        delete_num = min(d)
        while delete_num in d:
            new_list.append(delete_num)
            d.remove(delete_num)
    return new_list
 
 
list_a = [3, 45, 50]
list_b = [44, 43, 44]
list_c = merger(list_a, list_b)
print(list_c)
вывод
[3, 43, 44, 44, 45, 50]
1
3763 / 2814 / 1034
Регистрация: 21.03.2016
Сообщений: 7,156
22.11.2018, 18:31 3
с одним циклом
Python
1
2
3
4
5
6
def merger(a, b):
    new_list = []
    d = a + b
    while d:
        new_list.append(d.pop(d.index(min(d))))
    return new_list
1
1 / 1 / 0
Регистрация: 11.11.2018
Сообщений: 17
23.11.2018, 00:51  [ТС] 4
vlander, Ответ должен быть такой:
Test 1
input:
1 5 7
2 4 4 5
Wrong answer.
correct output:
1 2 4 4 5 5 7

Добавлено через 20 секунд
Semen-Semenich, Ответь такой должен быть

Test 1
input:
1 5 7
2 4 4 5
Wrong answer.
correct output:
1 2 4 4 5 5 7

Добавлено через 22 минуты
Semen-Semenich, и на 4 тесте показывает неправильный ответ Test 4
Wrong answer.

Добавлено через 8 минут
Semen-Semenich, vlander, Решил наконец задачу:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
lista = list(map(int, input().split()))
listb = list(map(int, input().split()))
 
 
def merge(a: list, b: list):
 
    lena = len(a)
    lenb = len(b)
 
    # если первый список длинее, то меняем
    # списки и переменные местами:
    if len(a) > lenb:
        a, b = b, a
        lena, lenb = lenb, lena
 
    i = 0   # индекс меньшего списка
    j = 0   # индекс большего списка
    listn = []   # новый список
 
    # цикл проходит только по меньшему списку:
    while i <= lena:
 
        # если конец одного из списка, то
        # добавляем оставшееся содержимое второго
        # списка в конец нового и выходим:
        if i == lena:
            listn = listn + b[j:lenb]
            return listn
        elif j == lenb:
            listn = listn + a[i:lena]
            return listn
 
        # проверяем числа списков и когда
        # берем число одного из списка в новый,
        # то увеличиваем соответствующий индекс:
        if a[i] < b[j]:
            listn.append(a[i])
            i += 1
        elif a[i] == b[j]:
            listn.append(a[i])
            listn.append(b[j])
            i += 1
            j += 1
        else:
            listn.append(b[j])
            j += 1
 
 
print(*merge(lista, listb))
1
29 / 21 / 8
Регистрация: 23.10.2018
Сообщений: 51
Записей в блоге: 3
23.11.2018, 07:51 5
А зачем такие сложности, ведь единый список проще сортировать, или у вас условия темы не позволяют это сделать?
0
3763 / 2814 / 1034
Регистрация: 21.03.2016
Сообщений: 7,156
23.11.2018, 18:49 6
Лучший ответ Сообщение было отмечено makishmaki как решение

Решение

makishmaki, странно. ответ тот который должен быть
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> def merger(a, b):
    new_list = []
    d = a + b
    while d:
        new_list.append(d.pop(d.index(min(d))))
    return new_list
 
>>> lista = list(map(int, input().split()))
1 5 7
>>> listb = list(map(int, input().split()))
2 4 4 5
>>> print(*merger(lista,listb))
1 2 4 4 5 5 7
>>>
1
1 / 1 / 0
Регистрация: 11.11.2018
Сообщений: 17
26.11.2018, 13:55  [ТС] 7
vlander, так коурсера требует)
0
1 / 1 / 0
Регистрация: 07.01.2019
Сообщений: 1
07.01.2019, 05:11 8
У меня на курсере так прошло:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge(a, b):
    c = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    while i < len(a):
        c.append(a[i])
        i += 1
    while j < len(b):
        c.append(b[j])
        j += 1
    return c
 
 
lista = list(map(int, input().split()))
listb = list(map(int, input().split()))
 
 
print(*merge(lista, listb))
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
33119 / 18460 / 3884
Регистрация: 12.02.2012
Сообщений: 31,028
Записей в блоге: 12
07.01.2019, 21:30 9
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge(a,b):
    na=len(a)
    nb=len(b)
    r=[]
    ia=0
    ib=0
    while (True):
        if (ia == na):
            for j in range(ib+1,nb):
                r+=[b[j]]
            break
        if (ib == nb):
            for j in range(ia+1,na):
                r+=[a[j]]
            break
        if a[ia] > b[ib]:
            r+=[b[ib]]
            ib+=1
        else:
            r+=[a[ia]]
            ia+=1
    return r
    
a=[1,3,5,7,9,10,11,12]
b=[2,4,6,7,8,9,13,15]
r=merge(a,b)
print(r)
1
Эксперт Python
4604 / 2025 / 359
Регистрация: 17.03.2012
Сообщений: 10,079
Записей в блоге: 6
09.01.2019, 10:49 10
Это элемент сортировки слиянием. Можете воспользоваться готовым решением.
0
1 / 1 / 0
Регистрация: 14.05.2020
Сообщений: 13
03.10.2020, 20:10 11
Самое быстрое и точное решение среди этих программ
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge(list1, list2):
    index1 = 0
    index2 = 0
    merged_list = []
    for _ in range(len(list1 + list2)):
        if index1 + 1 > len(list1):
            merged_list.append(list2[index2])
            index2 += 1
        elif index2 + 1 > len(list2):
            merged_list.append(list1[index1])
            index1 += 1
        elif list1[index1] < list2[index2]:
            merged_list.append(list1[index1])
            index1 += 1
        else:
            merged_list.append(list2[index2])
            index2 += 1
    return merged_list
 
 
numbers1 = [int(i) for i in input().split()]
numbers2 = [int(i) for i in input().split()]
print(*merge(numbers1, numbers2))
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.10.2020, 20:10
Помогаю со студенческими работами здесь

Слияние двух упорядоченных списков в один упорядоченный
Даны два списка упорядоченные по не убыванию.Объединить их в третий список упорядоченный по не...

Объединение двух упорядоченных по возрастанию массивов в один, также упорядоченный
Написать программу, которая объединяет два упорядоченных по возрастанию массива в один, также...

Образовать из элементов двух упорядоченных списков новый список, тоже упорядоченный
Даны два упорядоченных списка. Образовать из элементов этих списков новый список, также...

слияние двух упорядоченных массивов в один упорядоченный
это слияние двух упорядоченных массивов в один упорядоченный, программу я сама напишу, тока...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru