Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.57/21: Рейтинг темы: голосов - 21, средняя оценка - 4.57
0 / 0 / 0
Регистрация: 25.05.2017
Сообщений: 2

Проверить, есть ли в массиве хотя бы два элемента, ссылающихся на одинаковые числа

29.06.2017, 11:10. Показов 4005. Ответов 5

Студворк — интернет-сервис помощи студентам
Дан массив ссылок на вещественные числа. Написать программу для проверки, есть ли в массиве хотя бы два элемента, ссылающихся на одинаковые числа.
Никак не додумаюсь, как делать.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
29.06.2017, 11:10
Ответы с готовыми решениями:

Есть ли в массиве хотя бы два элемента, ссылающиеся на одинаковые числа
Доброго времени суток)) Нужна Ваша помощь. Задача такая: Дан массив ссылок на вещественные числа. Проверить, есть ли в массиве хотя бы...

Проверить, есть ли в списке хотя бы два одинаковых элемента
Доброго времени суток всем. Помогите, пожалуйста, переписать этот код на c++. Заранее спасибо. #include <iostream> #include...

Проверить, есть ли в списке хотя бы два одинаковых элемента
Написать логическую функцию, которая проверяет, есть ли в списке хотя бы два одинаковых элемента. Если условие выполняется, добавить новый...

5
4 / 4 / 2
Регистрация: 29.10.2015
Сообщений: 76
29.06.2017, 16:03
Хай, меня спрашивали такой вопрос на собеседовании, самый простой способ такой:
C#
1
2
3
4
5
6
7
8
9
10
  private bool CheckForDuplicates(Double[] array)
        {
            var result = false;
            for (int i = 0; i < array.Length - 1; i++)
                for (int j = i + 1; j < array.Length; j++)
                    if (array[i] == array[j])
                        return true;
                    
            return result;
        }
но он не очень оптимален, поэтому на собеседовании я ответил, что надо использовать хэш-таблицу, так в два раза быстрее:

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
 private bool CheckForDuplicates(Double[] array)
        {
            // создаём хэш-таблицу размерности равной величине массива
            LinkedList<Double>[] hashTable = new LinkedList<Double>[array.Length];
 
            foreach(var item in array)
            {
                // получаем хэш от значения
                var bytes = BitConverter.GetBytes(item);
                int sum = 0;
                foreach (byte b in bytes)
                    for (int i = 0; i < 8; i++)
                        sum += (b >> i) & 1;
                
                // ограничиваем значения хэша величиной массива
                int idx = sum % hashTable.Length;
 
                // инициализируем связный список в корзине хэш-таблицы
                if (hashTable[idx] == null)
                    hashTable[idx] = new LinkedList<double>();
 
                // если корзина еще пустая, то просто добавляем элемент
                if (hashTable[idx].First == null)
                {
                    hashTable[idx].AddLast(item);
                }
                // если корзина не пустая, то сверяемся с каждым элементов в связном списке
                else
                {
                    // получаем голову связного спика
                    var node = hashTable[idx].First;
                    var contains = false;
                    
                    // проходимся по нему
                    while (node != null)
                    {
                        // если значение имеется, то возвращаем true, дубль найден
                        if (node.Value == item)
                            return true;
 
                        // к следующему узлу связного списка корзины
                        node = node.Next;
                    }
                    // дубль не найден - значит коллизия, добавляем элемент в конец
                    hashTable[idx].AddLast(item);
                }
            }
            return false;
        }
Я вообще не особо мастер в этих делах, не могу сходу даже назвать O-большое для данного способа, возможно стоило подобрать другой размер хэш-таблицы, возможно вместо связного списка лучше было бы использовать дерево, но в 2 быстрее точно работает.

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

Да, кстати этот вариант проверяет массив именно на наличие одинаковых значений в нём, а не на равенство именно ссылок на значения, с проверкой на равенство именно ссылок что-то не могу сообразить сходу.
0
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
29.06.2017, 16:18
C#
1
            return array.Length != array.Distinct().Count();
0
Администратор
Эксперт .NET
 Аватар для OwenGlendower
18307 / 14231 / 5368
Регистрация: 17.03.2014
Сообщений: 28,904
Записей в блоге: 1
29.06.2017, 16:23
Цитата Сообщение от ribastar Посмотреть сообщение
возможно вместо связного списка лучше было бы использовать дерево
Почему бы не использовать HashSet<T>? С ним код станет гораздо короче.
0
4 / 4 / 2
Регистрация: 29.10.2015
Сообщений: 76
29.06.2017, 17:19
Цитата Сообщение от Diamante Посмотреть сообщение
C#
1
return array.Length != array.Distinct().Count();
класс, но самый медленный способ, не знаю что уж там под капотом Dsitinct();

Цитата Сообщение от OwenGlendower Посмотреть сообщение
Почему бы не использовать HashSet<T>? С ним код станет гораздо короче.
Ну чтобы продемонстрировать уровень пониже, а так сейчас проверил - да, действительно, самый быстрый способ такой:
C#
1
2
3
4
5
6
7
8
9
10
 private bool CheckForDuplicates4(Double[] array)
        {
            HashSet<Double> hashTable = new HashSet<Double>();
 
            foreach (var item in array)
                if (!hashTable.Add(item))
                    return true;
 
            return false;
        }
Быстрее всех вышеуказанных в несколько раз, тестировал на 10000000 элементах 10 попыток (вообще было проведено не очень корректное тестирование)

Интересно что под капотом у HashSet в случае коллизии? Как раз-таки дерево?
И наверняка хэш-функция какая-то быстрая, раз такие результаты;
0
Администратор
Эксперт .NET
 Аватар для OwenGlendower
18307 / 14231 / 5368
Регистрация: 17.03.2014
Сообщений: 28,904
Записей в блоге: 1
29.06.2017, 17:27
Цитата Сообщение от ribastar Посмотреть сообщение
Интересно что под капотом у HashSet в случае коллизии? Как раз-таки дерево?
Всего лишь два массива судя по исходному коду

Цитата Сообщение от ribastar Посмотреть сообщение
И наверняка хэш-функция какая-то быстрая
Double.GetHashCode
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
29.06.2017, 17:27
Помогаю со студенческими работами здесь

Проверить, есть ли в списке хотя бы два одинаковых элемента
Дан список А, состоящий из записей: первое поле – символ, второе – адрес следующего элемента. Составить программу, которая проверяет, есть...

Проверить, есть ли в списке хотя бы два одинаковых элемента
Народ, нужна помощь, как можно сделать проверку через булевскую переменную, добрался до списков, а с булевыми так и не довелось поработать...

Проверить, есть ли в списке хотя бы два одинаковых элемента
1. Проверить, есть ли в списке хотя бы два одинаковых элемента Помогите, пожалуйста, разобраться в чём проблема. Это же консольная...

Проверить, есть ли в списке L хотя бы два одинаковых элемента
1)Составить программу, которая проверяет, есть ли в списке L хотя бы два одинаковых элемента. 2) Составить программу, которая переносит в...

Проверить, есть ли в списке хотя бы два одинаковых элемента
Прошу проверить правильность кода и помочь написать его дальше. Написать программу, обеспечивающую работу с динамическими структурами -...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru