Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
6 / 5 / 1
Регистрация: 24.10.2018
Сообщений: 75
1

Самая простая задача на свете про сортировку

07.01.2019, 18:47. Просмотров 986. Ответов 4
Метки нет (Все метки)

Супер простая задача на сортировку. Дается N чисел (N ≤ 10^6), которые по абсолютной величине не превосходят 100.
Необходимо вернуть отсортированный массив. Эта задача решается с помощью сортировки подсчета, т.е за 1 проход по массиву подсчитать сколько раз встречаются цифры от -100 до 100.
Мой код:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
namespace Skyiv.Ben.Timus
{
    sealed class T1603a
    {
        static void Main()
        {
            var num = Console.ReadLine();  //Кол-во цифр которое я не использую
            var read = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); //Массив цифр
            var range = 201; //Длина массива от -100 до 100
            var answer = CountingSort(read, range); //Отсортированный массив
            for (var a = 0; a < answer.Length; a++) //Вывыожу каждый элемент 
                    for (var i = 0; i < answer[a]; i++) // такое кол-во раз которое он встечался
                        Console.Write(a - 100 + " ");
        }
 
        public static int[] CountingSort(string[] array, int range)
        {
            var tmp = new int[range];     //веду подсчет ...
            foreach (var i in array)
                tmp[100 + int.Parse(i)]++;
            return tmp;
        }
    }
}
Итог: я не могу решить эту задачу за 2 секунды, хотя есть кто решил на шарпе за 0,656. ХЕЛП!!!!

Ссылка на задачу почему то удалятся.
Задача на сайте acmp: 0041 Сортировка подсчетом
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.01.2019, 18:47
Ответы с готовыми решениями:

Простая задача про високосные года
Алоха! Недавно начал изучать руби, и столкнулся с такой ошибкой. Условие задачи: Високосные ...

Задача про сортировку слиянием
Помогите, пожалуйста! Изучаю алгоритмы программирования, сейчас на тема сортировки, конкретнее -...

Задача про матрицу и сортировку массива
Помогите пожалуйста решить задачу : Дана квадратная матрица. Получить одномерный массив...

Задача про сортировку массива и его вывод
Помогите пожалуйста решить задачку : Дана квадратная матрица 4х4. Сделать одномерный массив,...

4
SETI
63 / 48 / 18
Регистрация: 09.04.2018
Сообщений: 210
07.01.2019, 18:53 2
Mark0111, Можно задание полностью? А то ничего не понятно..При чем здесь сортировка, если надо подсчитать количество чисел между -100 и 100 в массиве?

Добавлено через 2 минуты
Цитата Сообщение от Mark0111 Посмотреть сообщение
Дается N чисел (N ≤ 10^6), которые по абсолютной величине не превосходят 100.
Цитата Сообщение от Mark0111 Посмотреть сообщение
подсчитать сколько раз встречаются цифры от -100 до 100
Все числа же.. тоесть N
0
6 / 5 / 1
Регистрация: 24.10.2018
Сообщений: 75
07.01.2019, 18:57  [ТС] 3
Самая простая задача на свете про сортировку

Ссылка удаляется почему то. Вот скрин задачи
0
Эксперт .NET
14697 / 11111 / 2919
Регистрация: 17.09.2011
Сообщений: 18,650
07.01.2019, 19:15 4
Лучший ответ Сообщение было отмечено Mark0111 как решение

Решение

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
using System.Text;
 
namespace Skyiv.Ben.Timus
{
    sealed class T1603a
    {
        static void Main()
        {
            var num = int.Parse(Console.ReadLine());
            var read = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); //Массив цифр
            var range = 201; //Длина массива от -100 до 100
            var answer = CountingSort(read, range); //Отсортированный массив
            var buffer = new StringBuilder(num * 4);
            for (var a = 0; a < answer.Length; a++) //Вывыожу каждый элемент 
                for (var i = 0; i < answer[a]; i++) // такое кол-во раз которое он встечался
                    buffer.Append(a - 100).Append(' ');
            Console.WriteLine(buffer);
        }
 
        public static int[] CountingSort(string[] array, int range)
        {
            var tmp = new int[range];     //веду подсчет ...
            foreach (var i in array)
                tmp[100 + int.Parse(i)]++;
            return tmp;
        }
    }
}
1
6 / 5 / 1
Регистрация: 24.10.2018
Сообщений: 75
07.01.2019, 19:18  [ТС] 5
kolorotur СПАСИБО!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2019, 19:18

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Задача про сортировку с использованием связного списка, нужно найти ошибку
Имеется файл состоящий из данных о студентах(ФИО, номер группы, средний бал). Построить...

Самая простая доработка 1С
Здравствуйте, может кто сможет выручить. Нужно сдавать курсовой по 1С. Тема доработка 1С, т.е....

Самая простая тема.
Всем привет! Скачал pgAdmin с оф.сайта (38мб) Запустил. Добавил сервер: хост localhost порт ...

Самая простая программа на Паскале
Здравствуйте, уважаемые форумчани. Помогите, пожалуйста, написать простую программу на Паскаль...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.