Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/20: Рейтинг темы: голосов - 20, средняя оценка - 4.60
kimed96
41 / 39 / 4
Регистрация: 25.06.2016
Сообщений: 278
1

Преобразование последовательности целых чисел

03.12.2018, 11:10. Просмотров 3717. Ответов 10

Добрый день!

Задача:

Дан массив целых чисел. Преобразовать его так, чтобы в начале последовательности были все нулевые значения, затем все положительные, потом все отрицательные. Порядок положительных и отрицательных чисел не должен быть нарушен. Массив преобразовывается на своем месте (дополнительный массив создавать нельзя).

Пример ввода-вывода:

Ввод: 6 -7 9 -3 0 5 -8 1 6 0

Ввод: 0 0 6 9 5 1 6 -7 -3 -8

Разработать наиболее эффективный алгоритм.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2018, 11:10
Ответы с готовыми решениями:

Преобразование последовательности чисел
Здравствуйте, подскажите пожалуйста как реализовать следующую задацу Есть последовательность...

В последовательности целых чисел, завершающейся нулем, возвести в квадрат те из них, значения которых отрицательны
В последовательности целых чисел, завершающейся нулем, возвести в квадрат те из них, значения...

Преобразование последовательности целых чисел по заданному правилу
Задано последованность целых чисел B(2n), n≤200.Создать программу,которая превращает эту...

В последовательности из n целых чисел все элементы уменьшить на минимальное число последовательности
Помогите, пожалуйста! Разработать и написать алгоритм указанной задачи. В последовательности из...

В последовательности целых чисел найти количество участков строгого возрастания последовательности и вывести на экран
В последовательности целых чисел найти количество участков строгого возрастания последовательности...

10
renat_dmitriev
390 / 292 / 121
Регистрация: 26.08.2016
Сообщений: 901
03.12.2018, 12:39 2
Тут нечего разрабатывать. Обычная сортировка. Подойдет любой существующий алгоритм сортировки, просто нужно выбрать какой будет быстрее работать для данной задачи.
1
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,654
03.12.2018, 13:29 3
Цитата Сообщение от kimed96 Посмотреть сообщение
Разработать наиболее эффективный алгоритм.
По времени или по памяти?
Если по времени, то создаём новый массив, переносим в него все нулевые значения, затем все положительные, потом все отрицательные.
1
renat_dmitriev
390 / 292 / 121
Регистрация: 26.08.2016
Сообщений: 901
03.12.2018, 13:39 4
Shamil1,
Массив преобразовывается на своем месте (дополнительный массив создавать нельзя).
2
03.12.2018, 13:39
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,654
03.12.2018, 14:02 5
Тогда сортировка вставками. Для больших массивов модифицированная сортировка слиянием. Для почти отсортированных - пузырьком. Других вариантов не вижу.

Добавлено через 2 минуты
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
Подойдет любой существующий алгоритм сортировки
нужна устойчивая сортировка
2
kimed96
41 / 39 / 4
Регистрация: 25.06.2016
Сообщений: 278
03.12.2018, 19:29  [ТС] 6
renat_dmitriev, Shamil1,

Сортировка не подойдет
Цитата Сообщение от kimed96 Посмотреть сообщение
Порядок положительных и отрицательных чисел не должен быть нарушен
0
renat_dmitriev
390 / 292 / 121
Регистрация: 26.08.2016
Сообщений: 901
03.12.2018, 21:02 7
kimed96, Сортировка не означает обязательно сортировать по значению чисел, условия сортировки вы можете задавать сами.
2
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,654
04.12.2018, 09:21 8
C#
1
2
3
string data = "6 -7 9 -3 0 5 -8 1 6 0";
var list = data.Split(' ').Select(x => int.Parse(x)).OrderBy(x => x > 0 ? 1 : (x < 0 ? 2 : 0));
Console.WriteLine($"{string.Join(" ", list)}"); // 0 0 6 9 5 1 6 -7 -3 -8
1
vrm2
325 / 220 / 59
Регистрация: 03.12.2015
Сообщений: 453
Завершенные тесты: 2
04.12.2018, 13:45 9
Цитата Сообщение от kimed96 Посмотреть сообщение
Разработать наиболее эффективный алгоритм.
1. Проходим по массиву и подсчитываем количество нулевых, положительных и отрицательных значений.
Теперь мы точно знаем, где в каком месте в результирующем массиве будут начинаться нулевые, положительные и отрицательные значения.

2. Берем элемент массива (по некому индексу i, для начала можно взять нулевой элемент), в зависимости от его значения ставим его на нужно место (по индексу j). Повторяем то же самое с элементом, который ранее стоял на месте j. Выполняем, пока не обработаем все элементы массива.

Нам понадобится три переменных, которые будут хранить индексы массива, куда нам надо записать следующее обрабатываемое число - для нулевых, положительных и отрицательных значений.

Итого. Два прохода по массиву - сложность по времени O(N). Дополнительная память не требуется

Добавлено через 1 минуту
Добавлено:

Не. По-моему, так не пойдет. Порядок элементов не сохранится
1
Дмитррр
40 / 24 / 3
Регистрация: 27.03.2016
Сообщений: 109
04.12.2018, 14:08 10
Цитата Сообщение от vrm2 Посмотреть сообщение
Порядок элементов не сохранится
Да всё проще.
Цикл для нулей:
Если нашёл ноль, то ставь его на первое место, все остальные значения массива (точнее не все, а только идущие от нового места нуля до его старого места) сдвигай на один дальше (задом наперёд, чтобы не потерять ничего).
Цикл для положительных:
Если нашёл плюс, то ставь его сразу на место последнего_нуля+порядковый_номер_плюсового (нули уже все посчитаны и переставлены), а все последующие опять же сдвигай на один.

Уж не знаю, наиболее это эффективный или нет, но по вычислениям вроде весьма просто. В одном цикле одновременно сортировать нули и знаки замысловатее.
1
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,654
08.12.2018, 14:36 11
Лучший ответ Сообщение было отмечено kimed96 как решение

Решение

Цитата Сообщение от Дмитррр Посмотреть сообщение
В одном цикле одновременно сортировать нули и знаки замысловатее.
Ничуть. Берём очередной элемент. Слева (отсортированная часть массива) находим место, на которое его нужно поставить. Ставим, сдвигая элементы между старой и новой позицией на 1 вправо. Называется сортировка вставками.
2
08.12.2018, 14:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2018, 14:36

В последовательности целых чисел найти количество чисел в которых нет 3 и 7 и наименьшее среди этих чисел
Разработать процедуру, которая в последовательности целых чисел находит количество чисел в которых...

Даны две последовательности целых чисел. Удалить из первой последовательности все элементы, встречающиеся во второй
Решить с помощью vector. Даны две последовательности целых чисел. Удалить из первой...

Преобразование последовательности чисел
Даны вещественные числа a1, a2,..., a2n. Получить a1, an+1, a2, an+2,..., an, a2n. Объясните,...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru