Здравейте, имам въпрос относно задача 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, които знания реално се проверяват на този етап, или се очаква да си намериш готово решение, за да преминеш успешно теста? При никоя от останалите задачи от примерните тестове не срещнах този проблем.
