C# Fundamentals - Mock exam 3 - Repeating Numbers

Здравейте, имам въпрос относно задача Repeating Numbers от Mock exam 3, част от курса c# Fundamentals. Условието е следното:

Repeating Numbers

Write a program that accepts an array of integers and returns the one that occurs the most times. If there are two numbers that occur the same amount of times, return the smaller of the two.

Input

  • Read from the standard input;
  • The number N is on the first line;
  • An integer between 1 and 10 is written on each of the next N lines;
  • The input data will always be valid and in the format described. There is no need to check it explicitly;

Output

  • Print to the standard output;
  • On the only output line you must print the number that occurs the most;

Constraints

  • The number N is a positive integer between 1 and 100 000, inclusive;
  • The list of numbers consists of positive integers between 1 and 10, inclusive;

Решението, което написах, работи с всички тест кейсове, но дава грешка Time Limit Exceeded в Judge, вероятно защото системата тества с N равен на няколко хиляди, при което двата For цикъла се забавят значително:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
string[] numbers = new string[n];

    int currentMax = 10;
    int maxCounter = 0;

    for (int i = 0; i < n; i++)
    {
        numbers[i] = Console.ReadLine();
    }
    for (int i = 0; i < n; i++)
    {
        int counter = 0;
        for (int ii = 0; ii < n; ii++)
        {
            if (numbers[i] == numbers[ii])
            {
                counter++;
            }
        }
        if (counter < maxCounter)
        {
            continue;
        }
        else if (counter == maxCounter)
        {
            if (currentMax < int.Parse(numbers[i]))
            {
                continue;
            }
            else if (currentMax > int.Parse(numbers[i]))
            {
                currentMax = int.Parse(numbers[i]);
                continue;
            }
        }
        else if (counter > maxCounter)
        {
            currentMax = int.Parse(numbers[i]);
            maxCounter = counter;
        }
    }
    Console.WriteLine(currentMax);
}

}

След около 30 секундно търсене открих готов метод за откриване на най - често повтарящ се елемент, който системата приема, но нямам идея какво точно прави:

var cnt = new Dictionary<int, int>();
foreach (int value in numbers)
{
if (cnt.ContainsKey(value))
{
cnt[value]++;
}
else
{
cnt.Add(value, 1);
}
}
int mostCommonValue = 0;
int highestCount = 0;
foreach (KeyValuePair<int, int> pair in cnt)
{
if (pair.Value > highestCount)
{
mostCommonValue = pair.Key;
highestCount = pair.Value;
}
}
Въпросът ми е, има ли как задачата да се напише използвайки само Arrays и Loops, които знания реално се проверяват на този етап, или се очаква да си намериш готово решение, за да преминеш успешно теста? При никоя от останалите задачи от примерните тестове не срещнах този проблем.

Здравей, има как да я решиш само с Array и For.
Ако не съм сигурен как да реша задачата, може би бих пробвал първо да намеря числото, което се среща най често и след това да Extend-на задачата, така че да намира двете най често срещани.

Има и друг, по tricky начин, да си направиш втори myIntArr int[] с 11 елемента, като за всяко едно число инкрементираш дадения индекс с 1.
myIntArr[currentNumber]++

Поздрави,
Мишо

Тази задачи изисква малко познания по DSA за оптимизиране на кода.

Тази задача се решава с 1 фор от 0 до < n със сложност O(n) + 10
image

От тук нататък трябва само да намерите двата иденкса с най големи числа от arr[] и да принтирате.

Избягвай да ползваш ii , по-добре ползвай друга буква , примерно j , отделно вътрешния цикъл трябва да започва от 1, ти така сравняваш 1 и съща позиция всеки път(аз лично предпочитам 1 цикъл като въртя до n-1 и вътре проверявам arr[i] == arr[i+1], по-тегаво е с вътрешен цикъл. Другото което е , че ти така се опитваш да сравниш последователни елементи 1-ви с 2-ри, 2-ри с 3-ти и т.н. … ако имаш 1 2 1 няма да сработи според мен, понеже 1-ците не са поредни. За да работи така масива трябва да е сортиран (има вградени методи за което, но може да се пробваш да го разпишеш ръчно) предварително. Иначе да , решава се задачата и без Dictionary , както вече е споменато :slight_smile:

Здравей :slight_smile:
Очаква се ти да намериш решение. Вярвам, че ако имаш желание да се занимаваш с девелъпмънт ще измисляш решения, а няма да очакваш Google да прави това.
Ако Google отговаря на всичко, защо сме ние и защо учим толкова много :blush:

Успех,
Диди

2 Likes

Опитайте с този подход : repeating-numbers - Pastebin.com
Създаваме масив, наречен frequency, с дължина 11. Индексите на този масив представляват числата от 1 до 10 и използваме масива, за да следим честотата на всяко число в масива numbers. Итерираме над масива с числа, като използваме цикъла foreach, и за всяко число увеличаваме съответния индекс в масива frequency.
След като изчислим честотата на всяко число, използваме друг цикъл, за да намерим числото, което се среща най-много пъти. Инициализираме maxFrequency на 0 и mostFrequentNumber на int.MaxValue, за да сме сигурни, че те ще бъдат актуализирани правилно. Извършваме итерация над индексите от 1 до 10 и сравняваме честотата на всяко число с maxFrequency. Ако някое число има по-висока честота, актуализираме maxFrequency и задаваме mostFrequentNumber на текущото число. Ако някое число има същата честота като maxFrequency, сравняваме числата и актуализираме mostFrequentNumber, ако текущото число е по-малко.Накрая отпечатваме mostFrequentNumber на стандартния изход.