Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.57/46: Рейтинг темы: голосов - 46, средняя оценка - 4.57
 Аватар для limeniye
1182 / 624 / 160
Регистрация: 19.04.2018
Сообщений: 2,923

Найти самую повторяющуюся букву в фразе

31.07.2021, 16:31. Показов 9785. Ответов 54
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте. Недавно писал решение задачи с поиском повторяющейся буквы(и сколько раз). Для этого мне пришлось сделать 2 итерации

- Как можно ускорить алгоритм?
- Можно ли сделать всё в одну строку(например через Linq)?

Добавлено через 55 секунд
Например решением для фразы "Hello world!" ответом будет "l" — 3 раза.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
31.07.2021, 16:31
Ответы с готовыми решениями:

Найти в массиве целых чисел самую длинную не повторяющуюся последовательность
Необходимо найти самую длинную серию. Серией называется последовательность различных чисел. Язык C#

Найти в строке самую длинную повторяющуюся подстроку
в паскаль найти в строке самую длинную повторяющую подстроку Добавлено через 11 минут Пожалуйста..очень сейчас нужно

Найти самую повторяющуюся цифру в массиве цифр
Дано N чисел и N цифр. Напишите программу которая находит самую повторяющуюся цифру в массиве . Входные данные ...

54
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
05.08.2021, 19:11
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от nicolas2008 Посмотреть сообщение
не стоит делать голословные заявления
Забавно, но к вам у меня аналогичное предложение.
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
05.08.2021, 20:06
Kazbek17, сортировку забыли.

Добавлено через 1 минуту
Цитата Сообщение от Kazbek17 Посмотреть сообщение
x.Count() > 1
Да и тут, полагаю, больше нуля. Иначе будет исключение, когда всех букв по одной в слове.
0
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
06.08.2021, 21:14
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
30
31
        static char Foo(string str) => str.ToLower().GroupBy(x => x).OrderByDescending(x => x.Count()).Select(x => x.Key).FirstOrDefault();
        static char Bar(string str)
        {
            var dict = new Dictionary<char, int>();
            foreach(var c in str.ToLower())
            {
                dict.TryGetValue(c, out int n);
                dict[c] = n + 1;
            }
            return dict.OrderByDescending(x => x.Value).FirstOrDefault().Key;
        }
        static void Main(string[] args)
        {
            var str = "Hello world!Hello world!Hello world!Hello world!Hello world!Hello world!Hello world!";
            Console.WriteLine(Foo(str));
            Console.WriteLine(Bar(str));
            var sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 10000; i++)
            {
                Foo(str);
            }
            sw.Stop();
            Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            sw.Restart();
            for (int i = 0; i < 10000; i++)
            {
                Bar(str);
            }
            sw.Stop();
            Console.WriteLine(sw.Elapsed.TotalMilliseconds);
0
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
07.08.2021, 09:01
Ну если уж заморочиться скоростью в самых минимальных единицах, то и не словарь, и не Linq. Самый обычный массив. В большинстве случаев в производительности у всех выиграет короткий массив.

В словаре - каждый раз придется проверить, существует ли ключ. Эта проверка делается быстро, но она выполняется на каждой итерации. Можно и не вызывать метод ContainsKey, но словарь все равно будет проверять ключ на null, вызывать Comparer и так далее. Все это дополнительные операции.

В массиве ничего проверять не нужно, сразу увеличиваем значение под нужным индексом.
Массив здесь будет явно быстрее, хотя дальнейшие операции иногда могут свести это преимущество на нет.

Дальнейшие операции - пробежаться по массиву/словарю одним проходом, чтобы найти максимальное значение. И здесь, словарь может оказаться короче массива, а может оказаться значительно короче. Это зависит от длины исходной строки и от набора символов, которые в нее входят. Если различающихся символов в строке мало и строка короткая, то в словаре будет мало значений, их можно быстро перебрать. Массив же будет длиной минимум 128. Если строка короткая, но содержит весь набор символов, то массив выиграет. Если строка длинная, то словарь проигрывает за счет количества операций на каждый символ. И чем длиннее строка, тем более заметна будет разница. На длине в сотни тысяч символов будет на порядок.

Один момент, который нужно учесть - в строке символы могут быть разные (из разных языков), и придется использовать массив значительно длиннее 128. В этом случае, если строка короткая - метод со словарем будет работать быстрее. Но если длинная или очень длинная, то на большом количестве операций словарь однозначно проиграет.

Linq будет еще медленнее словаря. В словарь символы добавляются за один проход. Идем по строке, проверяем, добавляем или увеличиваем значение. GroupBy подсчета не выполняет, нужен еще один метод - Count. Значит для каждой группы символов еще один проход по группе. Сортировку можно не учитывать, так как ее можно избежать, так же как в случае со словарем и массивом.

Вопрос, насколько чувствительно это будет, скажем чтобы не приходилось использовать измерительные средства, чтобы заметить разницу. На длинах примерно до 100 тыс. символов, это порядки тиков. Можно спокойно использовать любой способ, который удобнее, короче, больше нравится, более понятный и так далее. На очень больших длинах (миллионы символов) или очень большом количестве обрабатываемых строк, естественно разница очень даже будет. Но вопрос темы думаю, не о таком случае.
2
Эксперт .NET
 Аватар для Wolfdp
3790 / 1767 / 371
Регистрация: 15.06.2012
Сообщений: 6,543
Записей в блоге: 3
08.08.2021, 07:22
Цитата Сообщение от escoult Посмотреть сообщение
В большинстве случаев в производительности у всех выиграет короткий массив.
При условии что у нас не unicod. Иначе 255 символами не отделаешься.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16166 / 11286 / 2892
Регистрация: 21.04.2018
Сообщений: 33,175
Записей в блоге: 2
08.08.2021, 15:09

Не по теме:

Цитата Сообщение от wizard41 Посмотреть сообщение
__Corey,
ТС - ТопикСтартер (Topic Starter) - Автор топика (вопроса)
Не совсем так.
Аббревиатура из английских символов - сокращение от "Topic Caster".
Дословно можно перевести "Тот кто бросил тему (на обсуждение)".
По смыслу, конечно, просто "Автор темы".




Добавлено через 15 минут
Цитата Сообщение от escoult Посмотреть сообщение
Ну если уж заморочиться скоростью в самых минимальных единицах, то и не словарь, и не Linq. Самый обычный массив. В большинстве случаев в производительности у всех выиграет короткий массив.
Для данной задачи, вы не правы.
Поскольку на первой итерации (первым циклом) необходимо подсчитать количество вхождения КАЖДОГО символа из последовательности.
То есть обязательно возникает пара (символ, количество).
Словарь предлагает самый быстрый способ доступа к элементу по индексу отличному от целого числа.

На второй итерации (вторым циклом) необходимо выбрать пару с наибольшим значением количества.
Здесь так же ничего быстрее линейного перебора не придумаешь.

Массив, безусловно, будет быстрее словаря при доступе к единичному элементу.
Но для данной задачи придётся для индексов использовать код символа и размер массива (чтобы вошли все коды) должен быть ushort.MaxValue+1 = 216.
С таким массивом можно будет ускорить подсчёт количества.

Но для выбора максимального значения, придётся перебрать все 216 элементов.
А в словаре будут только символы имеющиеся в тексте и он, чаще всего, будет в сотни раз короче массива.

Поэтому массив может дать преимущество только если нужна обработка ОЧЕНЬ больших текстов и в этом тексте присутствуют очень много разных символ (количество сопоставимое с 216).

Добавлено через 2 минуты
Цитата Сообщение от escoult Посмотреть сообщение
В этом случае, если строка короткая - метод со словарем будет работать быстрее. Но если длинная или очень длинная, то на большом количестве операций словарь однозначно проиграет.
Не дочитал.
Вы и сами сделали подобный вывод.


Добавлено через 8 минут
Цитата Сообщение от limeniye Посмотреть сообщение
- Можно ли сделать всё в одну строку(например через Linq)?
Придётся группировать, сортировать группы по количеству и вывести первый (или последний) элемент.
Верное решение увидел только у Diamante (пост #43).
Чуть только можно изменить - для вывода не только символа, то и его количества.
C#
1
2
3
4
5
6
7
        static (char, int) Foo(string str)
        {
            var gr = str.GroupBy(x => x)
                        .OrderByDescending(x => x.Count())
                        .First();
            return (gr.Key, gr.Count());
         }
Если str null или Empty - будет исключение.
1
Эксперт .NET
 Аватар для Wolfdp
3790 / 1767 / 371
Регистрация: 15.06.2012
Сообщений: 6,543
Записей в блоге: 3
08.08.2021, 16:08
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Но для данной задачи придётся для индексов использовать код символа и размер массива
Я подозреваю что подразумевали все же такое решение:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = new int[255];
foreach(var ch in str)
    arr[(int)ch]++;
 
var max = arr[0];
var index = 0;
for(var i = 1; i < arr.Length; i++)
{
    if(arr[i] > max)
    {
        max = arr[i];
        index = i;
    }
}
Но как уже писали-- char вообще-то от U+0000 до U+FFFF
1
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16166 / 11286 / 2892
Регистрация: 21.04.2018
Сообщений: 33,175
Записей в блоге: 2
08.08.2021, 16:44
Цитата Сообщение от Wolfdp Посмотреть сообщение
Но как уже писали-- char вообще-то от U+0000 до U+FFFF
Да.
Надо увеличить размер: var arr = new int[ushort.MaxValue + 1];.
Но вот сколько займёт в нём поиск максимального?
Оправдается ли?

Добавлено через 59 секунд
И char к int явно, по-моему, не нужно приводить.
0
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
08.08.2021, 20:24
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Для данной задачи, вы не правы.
Поскольку на первой итерации (первым циклом) необходимо подсчитать количество вхождения КАЖДОГО символа из последовательности.
То есть обязательно возникает пара (символ, количество).
Пара и есть, индекс - значение.

Цитата Сообщение от Элд Хасп Посмотреть сообщение
Здесь так же ничего быстрее линейного перебора не придумаешь.
Я в посте все случаи рассмотрел, короткую строку, длинную, разный набор символов, и линейный поиск тоже.

Цитата Сообщение от Элд Хасп Посмотреть сообщение
Поэтому массив может дать преимущество только если нужна обработка ОЧЕНЬ больших текстов
Совершенно нет. Словарь может быть короткий, но он слишком дорогостоящий в сравнении с массивом. На длине в 10 тыс, никакого преимущества у него уже не будет. Это в случае, когда массив длиной 0xFFFF. Но это уже экзотика. Кому и зачем нужна вся плоскость полностью?

По условию задачи, строка вообще - английский текст. Ищем букву. Там хватит массива 128.
Понятно, что текст может быть разный, и языки разные, но вряд ли среди них будет Глаголица или Руны . Можно преспокойно ограничиться массивом 0x04FF. чтобы покрыть большинство распространенных алфавитов. А при такой длине массива - у словаря вообще нет шансов ни на каких длинах, даже в 10 символов.
1
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
09.08.2021, 03:49
Да и вообще эту проблему можно обойти, сделав все одним проходом.
Вот тест на малых длинах, с максимальной длиной массива и набором из разных блоков BMP:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
using System;
using System.Collections.Generic;
using System.Diagnostics;
 
namespace FrequencyMapArrayVsDictionary
{
    class Program
    {
        static void Main(string[] args)
        {
            var src = "abc FGK 22 yy !! xx HH ББ ЖЖЖЖ вн ДД уу \u2df0 \u30de ";
 
            //using array
            IFrequencyMeter fm1 = new FrequencyMeter();
 
            //using dictionary
            IFrequencyMeter fm2 = new AltFrequencyMeter();
 
            //start stop
            var sw = new Stopwatch();
            sw.Start();
            sw.Stop();
 
            //array
            sw.Restart();
            var res1 = fm1.MostFrequentLetter(src);
            sw.Stop();
 
            Console.WriteLine($"Array: {res1.symbol}({res1.count})   " +
                $"elapsed t`:{sw.ElapsedTicks,8:N0}   (Count: {fm1.Count})");
 
            //dict
            sw.Restart();
            var res2 = fm2.MostFrequentLetter(src);
            sw.Stop();
 
            Console.WriteLine($"Dict : {res2.symbol}({res2.count})   " +
                $"elapsed t`:{sw.ElapsedTicks,8:N0}   (Count: {fm2.Count})");
 
#if RELEASE
            Console.ReadKey();
#endif
        }
    }
 
    public interface IFrequencyMeter
    {
        int Count { get; }
        (char symbol, int count) MostFrequentLetter(string src);
    }
 
    public class FrequencyMeter : IFrequencyMeter
    {
        //Unicode BMP: 0000 - FFFF
        private const int _DEFAULT_SIZE = 0x1_0000;
        private readonly int[] _items;
        private int _count;
 
        private int _max;
        private int _maxIndex;
 
        public int Count => _count;
 
        //ctor
        public FrequencyMeter()
        {
            _items = new int[_DEFAULT_SIZE];
            _count = default(int);
            _max = default(int);
            _maxIndex = default(int);
        }
 
        public (char symbol, int count) MostFrequentLetter(string src)
        {
            if (src == null)
                throw new ArgumentNullException();
 
            foreach (var c in src)
            {
                if (char.IsLetter(c))
                {
                    _items[c]++;
                    if (_items[c] > _max)
                    {
                        _max = _items[c];
                        _maxIndex = c;
                    }
 
                    _count++;
                }
            }
 
            return ((char)_maxIndex, _max);
        }
    }
 
    public class AltFrequencyMeter : IFrequencyMeter
    {
        private readonly Dictionary<char, int> _frequencyMap;
        private int _count;
 
        private int _max;
        private char _maxKey;
 
        public int Count => _count;
 
        //ctor
        public AltFrequencyMeter()
        {
            _frequencyMap = new Dictionary<char, int>();
            _count = default(int);
            _max = default(int);
            _maxKey = default(char);
        }
 
        public (char symbol, int count) MostFrequentLetter(string src)
        {
            if (src == null)
                throw new ArgumentNullException();
 
            foreach (var c in src)
            {
                if (char.IsLetter(c))
                {
                    _frequencyMap.TryGetValue(c, out int n);
                    _frequencyMap[c] = n + 1;
 
                    if (n + 1 > _max)
                    {
                        _max = n + 1;
                        _maxKey = c;
                    }
 
                    _count++;
                }
            }
 
            return (_maxKey, _max);
        }
    }
}
Code
1
2
Array: Ж(4)   elapsed t`:   8 597   (Count: 25)
Dict : Ж(4)   elapsed t`:  30 972   (Count: 25)
Тест в Release.
При увеличении длины сохраняется примерно такое же 4-х кратное превосходство массива.
4
1152 / 860 / 263
Регистрация: 30.04.2009
Сообщений: 3,603
09.08.2021, 09:30
escoult, автор поста вроде ничего не говорил о возможности исключить арабские буквы, а они в конце таблицы.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16166 / 11286 / 2892
Регистрация: 21.04.2018
Сообщений: 33,175
Записей в блоге: 2
09.08.2021, 09:59
Цитата Сообщение от escoult Посмотреть сообщение
Да и вообще эту проблему можно обойти, сделав все одним проходом.
ТОЧНО!
Мне что-то это не пришло в голову.
Нужна же только максимальная комбинация, поэтому нет необходимости в сортировке ПОСЛЕ группировки.
Можно делать это сразу при подсчёте элементов.

На основе кода от Wolfdp:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
        public static (char, int)? MostFrequent(string str)
        {
            if (str == null)
                return null;
            if (str == string.Empty)
                return default((char, int));
 
            var arr = new int[ushort.MaxValue + 1];
            int max = 0;
            char letter = default;
            foreach (var ch in str)
            {
                var count = ++arr[ch];
                if (max < count)
                {
                    max = count;
                    letter = ch;
                }
            }
            return (letter, max);
        }
Ну и тоже самое с LINQ:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        public static (int[] arr, int max, char letter)? MostFrequentLinq(string str)
            => str?
                .Aggregate
                (
                    (arr: new int[ushort.MaxValue + 1], max: 0, letter: default(char)),
                    (t, ch) =>
                    {
                        var count = ++t.arr[ch];
                        if (t.max < count)
                        {
                            t.max = count;
                            t.letter = ch;
                        }
                        return t;
                    }
                );
2
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
23.08.2021, 18:59
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Не совсем так.
Аббревиатура из английских символов - сокращение от "Topic Caster".
Дословно можно перевести "Тот кто бросил тему (на обсуждение)".
По смыслу, конечно, просто "Автор темы".
Элд Хасп, зачем вводите людей в заблуждение? Дословно переведите слово Caster. И сравните с вашим
Цитата Сообщение от Элд Хасп
Тот кто бросил тему
На англоязычных форумах ТС (TS) отражает суть Топик Стартера, как я и сказал. Неожиданно(!), тому нашлось подтверждение даже здесь.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16166 / 11286 / 2892
Регистрация: 21.04.2018
Сообщений: 33,175
Записей в блоге: 2
23.08.2021, 19:56
Цитата Сообщение от wizard41 Посмотреть сообщение
На англоязычных форумах ТС (TS) отражает суть Топик Стартера

Спорить не буду - не вижу смысла.
Так как в любом случае это означает по смыслу одно и тоже.
Наверное имеет значение TC - написано латиницей (то есть ти-си) или кириллицей (то есть тэ-эс).
1
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
23.08.2021, 20:12
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Наверное имеет значение TC - написано латиницей (то есть ти-си) или кириллицей (то есть тэ-эс).
Да, похоже дело в этом. Я не ради спора, не обессудьте. Просто никогда не встречал TopicCaster.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
23.08.2021, 20:12

Найти самую длинную подстроку повторяющуюся в тексте и подсчитать количество символов подстроки
подскажите плез может что-то надо исправить а может я вобще по ложному следу пошёл u='' s='aaaa' i=0 e=0 j=2 while...

Строка: вывести на экран самую повторяющуюся комбинацию символов.
Здравствуйте! Нужна помощь в решении задачи по программированию (с++). Дана строка из повторяющихся комбинаций символов например:...

Найти слово в фразе из 3 слов, которое начинаеться на букву "M"
Необходимо найти слово в фразе из 3 слов, которое начинаеться на букву &quot;M&quot;(на английском). Нужно, чтобы это слово вывело отдельно от...

найти в тексте самую встречаемую букву
как сделать?

Найти в тексте слова, содержащие самую распространенную букву текста
В текстовом файле input.txt записан русский текст. Найти в тексте слова, содержащие самую распространенную букву текста не менее двух раз,...


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

Или воспользуйтесь поиском по форуму:
55
Ответ Создать тему
Новые блоги и статьи
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru