Сортировка строк по количеству символов

Question

Пример данных: вход: "abcdacdc" Вывод: "cadb" здесь мы должны отсортировать строки в порядке количества символов. Если счет одинаков для персонажей. поддерживать первоначальный порядок символы из входной строки.

мой подход: я использовал массив из 26 для поддержания вхождения всех символов и отсортировал его, затем напечатал его. Но при этом я не могу поддерживать порядок в случае, если два символа имеют одинаковое количество.

Пожалуйста, предложите любое улучшение или любой другой алгоритм.

Answer 1

На каком языке, например, в c # вы можете сделать это просто так:

var strstr = "abcdacdc";
var sortedString = new string(strstr
                              .OrderByDescending(x => strstr.Count(p=>p==x))
                              .Distinct().ToArray());

алгоритм очевиден (в цикле for вы можете сделать то же самое).

Edit: сначала мы сортируем все символы строки по их количеству, после этого мы собираемся использовать символы без повторяющихся элементов (метод Distinct).

    private struct CharCount
    {
        public int count;
        public char ch;
    }

    List<CharCount> sortedChars = new List<CharCount>();
   for(int i=0;i<strstr.Length;i++)
   {
       if (sortedChars.FindIndex(x => x.ch == strstr[i]) < 0)
       {
         int charcount = GetCharCount(strstr, strstr[i]);
         sortedChars.Add(new CharCount {count = charcount, ch = strstr[i]});
       }
   }

   string sortedstr2 = new string(sortedChars.OrderByDescending(x => x.count).Select(x=>x.ch).ToArray());

Вы можете реализовать метод GetCharCountкак у вас, массив из 26 символов и ..., так что выше алгоритмы сначала для цикла это O (n ^ 2) и последний абзац (сортировка) это O (n log (n)) во всех это O (n ^ 2),Вы можете просто изменить последний абзац так, как вы хотите (на вашем конкретном языке).