5. Top Integers Exercise: Arrays - C# Fundamentals - май 2020 - Софтуерен университет

Ankoun1 18 Точки

5. Top Integers Exercise: Arrays - C# Fundamentals - май 2020

Има ли по удачна функция за тази задача от All() за бързо решение

using System;
using System.Collections.Generic;
using System.Linq;

namespace dey_of_week
{
class Program
{
static void Main(string[] args)
{
List<int> arr = Console.ReadLine().Split().Select(int.Parse).ToList();

while (arr.Count != 0)
{
if (arr.All(x => x <= arr[0]))
{
int element = arr[0];
arr.RemoveAt(0);
if (arr.All(x => x < element))
{
Console.Write(element + " ");
}
}
else
{
arr.RemoveAt(0);
}
}

}
}
}

Тагове:

26/06/2020 18:53:07 Fundamentals Module 26/06/2020 19:13:30

MartinBG 4803 Точки

Предложеното решение не е от оптималните, защото ще обходи елементите повече от веднъж, като при това ще модифицира списъка на всяка итерация:

N-пъти ще мине през while цикъла, като при всяко минване ще обхожда оставащите елементи в списъка и ще трие първия елемент, което допълнително води до забавяне.

Ако разгледаме дадените примери (напр. 14 24 3 19 15 17), бързо ще открием, някои зависимости:

- последното число в масива винаги е валидно - 17

- следващото валидно число, преди последното, е това, което е по-голямо от него - 19

- следващото валидно число, преди горното такова трябва да е по-голямо от него - 24

- и т.н.

Ако изходим от горните наблюдения, може да напишем решение, което само с едно единствено обхождане на списъка (отзад напред), ще може да изведе всички числа, които отговарят на изискването.

Примерен псевдо-код:

numbers = [14 24 3 19 15 17];

last = numbers[numbers.size -1]; // 17

result.append(last); // 17

for (i = numbers.size - 1; i >= 0; i--) {

  if (numbers[i] > last) {
    last = numbers[i]
    result.append(last); // 19, 24
  }
}

print(result.reverse)

26/06/2020 21:51:19 26/06/2020 21:54:28

Iv_Konov 383 Точки

Здравей, Ankoun1,

решението ти е добро... Тъкмо направих едно решение при 100/100, ако не ти харесва, продължавай да чакаш друг вариант.

Разбира се, решението ми не е идеално - особено при огромни входни данни/числа. Това е предвид текста на @MartinBG:
"N-пъти ще мине през while цикъла, като при всяко минване ще обхожда оставащите елементи в списъка
и ще трие първия елемент, което допълнително води до забавяне."

14 24 3 19 15 17 24

===

using System;
using System.Collections.Generic;
using System.Linq;

namespace _0._1_Test
{
class Program
{
static void Main(string[] args)
{
List<int> list = Console.ReadLine().Split().Select(int.Parse).ToList();

while (list.Count != 0)
{
Console.Write(list.Max() + " ");

list.RemoveRange(0, list.LastIndexOf(list.Max()) + 1);
}
}
}
}
===

Поздрави,

Иван

п.с. добавил съм bold/подчертан текст

28/06/2020 00:00:08 28/06/2020 09:25:29

MartinBG 4803 Точки

Хубаво и кратко решение, но за съжаление и то страда от проблемите, които съм описал в поста си.

Представете си следните входни данни:

9 8 ... 1 0

10 числа, всичките отговарящи на условието.

В резултат, на всяка итерация ще се обхождат всички оставащи числа (за да се намери най-голямото) и после списъка се модифицира, като се изтрива първото число, (ако не говорим за LinkedList, това е най-скъпата възможна модификация).

10 числа не са много, но входните данни може и да са:

1000000 999999 ... 1 0

Разбира се, в Judge няма подобен тест, а и в този курс не се налага да се пишат оптимизирани решения за да минат.

Подозирам, че колегата @Ankoun1 под "бързо решение" има предвид такова, което е по-кратко като код, но все пак оставям отговора си за колегите, които се интересуват и от оптимизирано откъм бързодействие и/или използвани системни ресурси такова.

28/06/2020 01:14:06

Iv_Konov 383 Точки

@MartinBG,
разбира се, идеити ви са много добри и... не само за тази задача! Практически и други колеги
са ми споменавали да се ползват оптимални решения предвид огромни входни данни. Ученето е нужно...!

Поздрави,
Иван :)

28/06/2020 09:28:55