9.Most Frequent Number - java - Софтуерен университет

cvet_yordanova 2 Точки

9.Most Frequent Number - java

Здравейте,

Условието на задачата е:

1. Most Frequent Number

Write a program that finds the most frequent number in a given sequence of numbers.

Numbers will be in the range [0…65535].
In case of multiple numbers with the same maximal frequency, print the left most of them.

Понеже задaчата е към секцията Arrays и ми се иска да я реша просто с int[]. Само че с това решение ми гърми за време. Та някой може ли да преложи нещо простичко без листове и други такива :)

https://judge.softuni.bg/Contests/255/Java-Basics-Exercises

Тагове:

13/05/2017 11:26:24 Module: Java Advanced 13/05/2017 11:30:06

Виж всички отговори

Vladix 75 Точки

Здравейте,

Първото, което ми идва на ум ако искаш да го решиш само с масиви, е да си направиш един масив int[] arr = new int[65535];

, в който ще пазиш всяко число колко пъти се е появило, т.е ако имаш 1, 2, 111, 1234 ще си увеличаваш клетниките на тези индекси += 1; (arr[1]++; arr[2]++; arr[111]++; arr[1234]++ тн). След това ще си обходиш масива и ще видиш всяко едно число колко пъти се е повторило и ще си вземеш The Most Frequent Number

Поздрави

13/05/2017 11:52:42

cvet_yordanova 2 Точки

https://pastebin.com/E4wSygWk

С моя for loop, дето съм го направила да си взема най-голямото число от positions[] и да му взема мястото в редицата се разваля второто условие на задачата и дава 90/100. Понеже в positions[] индексите са си подредени и ако дам 1,2,1234,1234,111,111, то ще ми даде 111, защото е по-малко и е по-напред в positions[], а в условието искат най-лявото, дето са ми дали, т.е 1234...ии пак трябва помощ..има ли методче или нещо там в света на жава ;dd да си взема от int[] редица позицията на дадено число :))

13/05/2017 13:06:19

Vladix 75 Точки

Ами може да пазиш текущото най - повтарящо число и да си го променяш. Аз си мислех, че трябва да е най - малкото. Не мисля че има някво такова готово методче :Д

Поздрави

13/05/2017 13:37:48

Lyubomir_Georgiev 1 Точки

Задачата се решава на 20 реда с Hashtable<Integer,Integer> за 100/100.

Итерира се по всички елементи и за всеки се проверява дали има вече такъв Ключ, ако има инкрементираме стойността, а ако няма създаваме нов със стойност 1. При всчка итерация следим дали получената стойност е по-голяма от най-голямата стойност сетвана до момента, по този начин отговаряме на втората част на условието.

Ако се пробвате с HashtМап<Integer,Integer> дава 90/100 гърми за време на един тест.

04/04/2018 20:14:58

MartinBG 4803 Точки

@Lyubomir_Georgiev

Подходът с HashMap разбира се е валиден, но конкретно за тази задача се предполага да се използва решение като предложненото от Vladix: масив от 65535 целочислени елемента (напр int[65535]), като всеки елемент в масива се използва като брояч за срещанията на числото с неговия индекс.

Това решение е и добра препратка към един специфичен и доста оригинален алгоритъм за сортиране - Counting Sort.

05/04/2018 09:51:42

Виж всички отговори