Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
SeREGaGLaZ
1 / 1 / 2
Регистрация: 18.10.2013
Сообщений: 38
1

Какое место число занимает в существующем ряду введенных чисел, если бы они были отсортированы по возрастанию?

23.07.2014, 22:36. Просмотров 506. Ответов 6
Метки нет (Все метки)

Суть в следующем:
С клавиатуры вводится большое количество чисел (их может быть несколько десятков тысяч)
Вводятся они в не сортированном порядке.
После ввода очередного числа мне нужно узнавать какое место оно занимает в существующем ряду введенных чисел, если бы они были отсортированы по возрастанию.

Например ряд чисел: 1 4 6 2 8 0
после ввода 1 я узнаю, что оно первое,
после ввода 4 - что второе
после ввода 6 - что третье
после ввода 2 - что второе
после ввода 8 - что пятое
после ввода 0 - что первое

Прочитал что класс TreeSet сразу забивает данные в отсортированном порядке, но без итерала я не смогу узнавать какое по счету очередное число, а если пользоваться ArrayList и искать циклом for подходящее место, то вставляя туда элемент, все остальные элементы большие него будут долго переставляться на шаг вперед.

Кто-нибудь может мне подсказать, что делать?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2014, 22:36
Ответы с готовыми решениями:

Какое место на соревнованиях занял каждый из юношей, если все они заняли разные места
В соревнованиях по плаванию участвовали Андрей, Виктор, Саша и Дима. Их друзья высказали...

В десяти полях Edit переставить местами числа так, чтобы они были отсортированы по убыванию.
В десяти полях Edit переставить местами числа так, чтобы они были отсортированы по убыванию. ...

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

Преобразовать строку так, чтобы все буквы в ней были отсортированы по возрастанию
Задана строка, состоящая из символов. Символы объединяются в слова. Слова друг от друга отделяются ...

Переставить строки матрицы так, чтобы элементы последнего столбца были отсортированы по возрастанию
Срочно понадобилась помощь! Дано такое условие: Переставить строки матрицы так, чтобы элементы...

6
KEKCoGEN
Эксперт Java
2247 / 2094 / 536
Регистрация: 28.12.2010
Сообщений: 8,267
23.07.2014, 23:24 2
Как вы себе представляете ввод 10000 чисел с клавиатуры? Есть какое то максимальное число которое может быть введено?
0
SeREGaGLaZ
1 / 1 / 2
Регистрация: 18.10.2013
Сообщений: 38
23.07.2014, 23:55  [ТС] 3
Предположим 60 000.
Конечно вводить вручную никто их не будет.
Ввод будет производиться автоматически через консоль, либо чтение из файла,
меня интересует именно реализация алгоритма.
0
KEKCoGEN
Эксперт Java
2247 / 2094 / 536
Регистрация: 28.12.2010
Сообщений: 8,267
24.07.2014, 01:11 4
у вас выбор стоит по-сути в затратах памяти или затратах времени. Например вы можете создать массив длинной в 60к ячеек и добавлять число в соотв. ячейку О(1) по времени. Затратно по памяти, но быстро по времени.

С другой стороны если экономить память, можно класть элементы в какой нибудь LinkedList и тогда при каждой вставке надо будет искать куда вставить элемент O(n) по времени.

Если максимальное кол-во элементов заранее неизвестно, первое решение конечно же не подойдет
0
Pablito
2860 / 2273 / 767
Регистрация: 12.05.2014
Сообщений: 7,978
Завершенные тесты: 1
24.07.2014, 09:47 5
а если сделать так?
Цитата Сообщение от SeREGaGLaZ Посмотреть сообщение
После ввода очередного числа мне нужно узнавать какое место оно занимает в существующем ряду введенных чисел, если бы они были отсортированы по возрастанию.
Например ряд чисел: 1 4 6 2 8 0
после ввода 1 я узнаю, что оно первое,
после ввода 4 - что второе
если бы они были отсортированы, то 4 было бы не на второй позиции, а на 3 и так далее, я не понял условие или оно поставлено неверно?
0
KEKCoGEN
Эксперт Java
2247 / 2094 / 536
Регистрация: 28.12.2010
Сообщений: 8,267
24.07.2014, 11:04 6
Цитата Сообщение от Паблито Посмотреть сообщение
если бы они были отсортированы, то 4 было бы не на второй позиции, а на 3
На момент введения чисел 1 4, 4 находится на первой позиции(если считать позиции с нуля) . На третью оно смещается только после того как вставили 2 и 0

Добавлено через 8 минут
Если подумать, решение с TreeSet выглядит все же быстрее т.к TreeSet гарантирует вставку элемента за O(logN) что быстрее чем вставка к лист.
0
SeREGaGLaZ
1 / 1 / 2
Регистрация: 18.10.2013
Сообщений: 38
24.07.2014, 13:35  [ТС] 7
Абсолютно верно.
Но в TreeSet к тому же нельзя хранить одинаковые элементы, а мне необходимо хранить одинаковые элементы.
0
24.07.2014, 13:35
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2014, 13:35

Преобразовать строку таким образом, чтобы буквы каждого слова в ней были отсортированы по возрастанию
Привет всем! Сломал я ногу и 4 месяца не ходил в универ,теперь мне задали задания,я даже примерно...

Изменить последовательность столбцов матрицы так, чтобы элементы их первой строки были отсортированы по возрастанию
Срочно понадобилась помощь! Дано такое условие: Исходные данные: Изменить последовательность...

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


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

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

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