например есть "vvabbcbcc"
Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
Есть какой-то быстрый способ? Мне дали 5 минут написать метод

Здравствуйте, Аноним, Вы писали:

А>например есть "vvabbcbcc"
А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод
отсортировать не вариант?

Здравствуйте, Blazkowicz, Вы писали:
отсортировать я знаю ( два цикла , временная переменная для "свапа" — довольно просто)
Вот именно сгруппировать и сохранить последовательность.
Я похоже сделаю(придумаю "алгоритм") — но время 5 мин!!! Может это решенное ?

B>Здравствуйте, Аноним, Вы писали:

А>>например есть "vvabbcbcc"
А>>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>>Есть какой-то быстрый способ? Мне дали 5 минут написать метод
B>отсортировать не вариант?

Здравствуйте, Аноним, Вы писали:

А>например есть "vvabbcbcc"
А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод

Если плевать на память, и лишь бы работало за 5 мин. — то ЛинкедХешМап поможет

Здравствуйте, PZI, Вы писали:

Хоть намекните как?

PZI>Здравствуйте, Аноним, Вы писали:

А>>например есть "vvabbcbcc"
А>>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>>Есть какой-то быстрый способ? Мне дали 5 минут написать метод

PZI>Если плевать на память, и лишь бы работало за 5 мин. — то ЛинкедХешМап поможет

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, PZI, Вы писали:

А>Хоть намекните как?

PZI>>Здравствуйте, Аноним, Вы писали:

А>>>например есть "vvabbcbcc"
А>>>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>>>Есть какой-то быстрый способ? Мне дали 5 минут написать метод

PZI>>Если плевать на память, и лишь бы работало за 5 мин. — то ЛинкедХешМап поможет

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

LinkedHashMap

в качестве ключа буква, в качестве значения количество вхождений.

бежиш по строке с лева на право.

потом итерируешся по мапу (он сохраняет порядок добавления)

On 21.02.2013 18:36, PZI wrote:

> Бежишь по строке и считаешь, что каждый символ это ключ. Вытаскиваешь из
> мапки по этому ключу значение, которое из себя представляет
> целочисленное число(количество повторений), если нет такого значения,
> добавляешь со значением 1, если есть — инкрементишь.
Это всего-лишь гистограмма. Жесть, так ее обозвать — ЛинкедХешМап.
А зачем мапка?

Здравствуйте, Аноним, Вы писали:

А>например есть "vvabbcbcc"
А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод
Считаешь количество в цикле начиная с первой.. Уже посчитаные превращаешь в пустое что б не путалось.. Восстанавливать совсем легко.. Каждую букву столько раз сколько она встретилась..

Здравствуйте, Vzhyk, Вы писали:

V>On 21.02.2013 18:36, PZI wrote:

>> Бежишь по строке и считаешь, что каждый символ это ключ. Вытаскиваешь из
>> мапки по этому ключу значение, которое из себя представляет
>> целочисленное число(количество повторений), если нет такого значения,
>> добавляешь со значением 1, если есть — инкрементишь.
V>Это всего-лишь гистограмма. Жесть, так ее обозвать — ЛинкедХешМап.

Название отражает именно то, что она из себя представляет.

V>А зачем мапка?

Ваши варианты?

On 21.02.2013 21:34, PZI wrote:

> Название отражает именно то, что она из себя представляет.
Карта, связанная хешем? Не, построить гистограмму сильно понятнее.

> Ваши варианты?
Массив.

On 21.02.2013 21:34, PZI wrote:

> V>А зачем мапка?
>
> Ваши варианты?
Точнее, мапка имеет смысл, если символы могут быть любыми из UTF8,
фактически ею мы проэмулируем разреженный массив.
Если же мы в небольшом алфавите, то нафиг не нужна.

Здравствуйте, Vzhyk, Вы писали:

V>On 21.02.2013 21:34, PZI wrote:

>> Название отражает именно то, что она из себя представляет.
V>Карта, связанная хешем? Не, построить гистограмму сильно понятнее.

Причем тут гистограмма?
Вы как я понимаю, мимо проходили и к жабе отношения не имеете? — тут почитайте

>> Ваши варианты?
V>Массив.
Дальше развейте плиз мысль. Свою мапку изобретать будем?

Здравствуйте, Vzhyk, Вы писали:

V>On 21.02.2013 21:34, PZI wrote:

>> V>А зачем мапка?
>>
>> Ваши варианты?
V>Точнее, мапка имеет смысл, если символы могут быть любыми из UTF8,
V>фактически ею мы проэмулируем разреженный массив.
V>Если же мы в небольшом алфавите, то нафиг не нужна.

вот это как раз и есть жесть...

On 21.02.2013 21:57, PZI wrote:

> вот это как раз и есть жесть...
Почему?

Здравствуйте, Vzhyk, Вы писали:

V>On 21.02.2013 21:57, PZI wrote:

>> вот это как раз и есть жесть...
V>Почему?

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

On 21.02.2013 22:04, PZI wrote:

> да мне бы просто даже в голову не пришло закладываться на однобайтные
> кодировки.
Я говорил про размер алфавита, который следует обрабатывать.
И в зависимости от данных, можно обойтись одним массивом, двумя,
разреженным массивом, мапой.
Все зависит от конкретной задачи. Лично я бы мапу рассматривал последней.

Здравствуйте, Аноним, Вы писали:

А>например есть "vvabbcbcc"
А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод

2 массива размером character set (т.е. 256 для ASCII) — один массив счетчиков и один массив для хранения последовательности. O(n).

You will always get what you always got
  If you always do  what you always did

On 22.02.2013 13:23, jazzer wrote:

> 2 массива размером character set (т.е. 256 для ASCII) — один массив
> счетчиков и один массив для хранения последовательности. O(n).
Затем тебе 256, если алфавит английского около 30?

Здравствуйте, Аноним, Вы писали:

А>например есть "vvabbcbcc"
А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"

Все передельно просто и понятно. Решается за O(n) по времени и O(2*размер_словаря) по памяти. Решение: 2 массива размера словаря, один для подсчета элементов, второй для запоминания последовательности появления элементов. Идем по исходному массиву и делаем для каждого из элементов, если в массиве для подсчета занчение не нулевое, то увеличиваем его на 1; если нулевое — увеличиваем на 1 и добавляем элемент в массив восстановления последовательности. Восстанавливаем массив.

А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод

И ты не справился??? Лишний раз убеждаюс в правильности таких вопросов