Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / WinForms, .Net Framework Новый топик    Ответить
 Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Slant-shadow
Member

Откуда:
Сообщений: 292
Всем привет.
Можете помочь написать такой алгоритм, нужно в одном массиве найти повторяющиеся элементы, а затем вставить в другой массив только уникальные элементы из первого массива.
20 июн 15, 16:56    [17797244]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Shocker.Pro
Member

Откуда: ->|<- :адуктО
Сообщений: 17603
      var arr = new[] { 3, 4, 8, 7, 4, 2, 3 };

      var arr1 = arr
        .GroupBy(n => n, (n, m) => new { Key = n, Cnt = m.Count() })
        .Where(n => n.Cnt > 1)
        .Select(n => n.Key)
        .ToArray();

      var arr2 = arr
        .GroupBy(n => n, (n, m) => new { Key = n, Cnt = m.Count() })
        .Where(n => n.Cnt == 1)
        .Select(n => n.Key)
        .ToArray();

      Console.WriteLine(string.Join(",", arr1));
      Console.WriteLine(string.Join(",", arr2));
20 июн 15, 17:07    [17797263]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Slant-shadow
Member

Откуда:
Сообщений: 292
Без использования Linq нужно
20 июн 15, 17:24    [17797314]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Shocker.Pro
Member

Откуда: ->|<- :адуктО
Сообщений: 17603
Slant-shadow
Без использования Linq нужно
огласите весь список "без использования", пожалуйста. А то может без использования C# нужно. Хотя может быть нужно сделать без чужой помощи, самому?
20 июн 15, 17:26    [17797320]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
Однопроходный цикл - без группировок и пересортировок - минимальный расход времени и ресурсов
  
           int[]  arr={325,3245,5,54325,5,465326,7,214,325, 7} ;

            List<int> uniq = new List<int>(); // список уникальных
            List<int> dbls = new List<int>(); // список неуникальных
            for (int i = 0; i < arr.Length; i++)
            {
                if(  !uniq.Contains(arr[i]) )
                { //если нет ни в одном списке  - заносится в уникальный
                    if( !dbls.Contains(arr[i])) { uniq.Add(arr[i]);}
                }
                else 
                {  //если уже есть в списке уникальных
                   //- удаляется оттуда и вносится в список неуникальных но только один раз
                    uniq.Remove(arr[i]) ;
                    dbls.Add(arr[i]) ;
                }
            }

            int[] arr_uniq = uniq.ToArray();


Для фанатов генериков - код внутри for(){...} можно вынести в отдельную Action,
и вместо наглядного цикла использовать однострочную Array.Foreach

       static  void CheckUinq(int val, ref List<int> auniq, ref List<int> adbls)
        {
            if (!auniq.Contains(val))
            { //если нет ни в одном списке  - заносится в уникальный
                if (!adbls.Contains(val)) { auniq.Add(val); }
            }
            else
            {  //если уже есть в списке уникальных
               //- удаляется оттуда и вносится в список неуникальных но только один раз
                auniq.Remove(val);
                adbls.Add(val);
            }
        }
...

     Array.ForEach<int>(arr, v => CheckUinq(v, ref  uniq, ref dbls));
20 июн 15, 21:07    [17797897]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Dima T
Member

Откуда:
Сообщений: 11465
Сортируешь и идешь последовательно, если текущий равен предыдущему - пропускаешь.
20 июн 15, 21:08    [17797901]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
Dima T
Сортируешь и идешь последовательно, если текущий равен предыдущему - пропускаешь.


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

Но стоит отметить, что
- пересортировка больших массивов - это время и ресурсы.
- полностью теряется исходная последовательность чисел в массиве - во многих прикладных задачах (вычисление корреляций, криптоанализ) - это недопустимо
20 июн 15, 21:23    [17797961]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Изопропил
Member

Откуда:
Сообщений: 30649
ZhV
полностью теряется исходная последовательность чисел в массиве

не увидел подобного требования в условиях задачи
20 июн 15, 21:43    [17798032]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Dima T
Member

Откуда:
Сообщений: 11465
ZhV
Dima T
Сортируешь и идешь последовательно, если текущий равен предыдущему - пропускаешь.


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

Хоть 100500 подряд одинаковых. Достаточно текущий с предыдущим сравнить. Последующий станет текущим на следующем шаге.

ZhV
Но стоит отметить, что
- пересортировка больших массивов - это время и ресурсы.

Тупой перебор это еще больше времени и ресурсов. Дешевле сначала отсортировать.
ZhV
- полностью теряется исходная последовательность чисел в массиве - во многих прикладных задачах (вычисление корреляций, криптоанализ) - это недопустимо

Если недопустимо, то сначала копия потом ее сортируй. Или строй индекс.
20 июн 15, 21:47    [17798047]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
Dima T
Хоть 100500 подряд одинаковых. Достаточно текущий с предыдущим сравнить. Последующий станет текущим на следующем шаге.

Оцените сами - вот пример отсортированной последовательности
0 - 345 - не равен предыдущему - true
1 - 456 - не равен предыдущему - true
2 - 456 - равен предыдущему - false
3 - 467 - не равен предыдущему - true

Итак - число 456 с индексом 1 - условие выполняется, но число то не уникально в последовательности и условие задачи не выполняется

Dima T
Тупой перебор это ...


Array.Contains работает на "нижайшем уровне" - команды ассемблера scasb или scasw (сканирование области памяти на поиск совпадений) работают очень быстро.
20 июн 15, 22:07    [17798122]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Где-то в степи
Member

Откуда: Под Таганрогом
Сообщений: 4244
Slant-shadow,
перегони свой массив в HashSet<T> и получишь в нем уникальные, надо знать фундаментальные типы гы
20 июн 15, 22:41    [17798231]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
eny
Member

Откуда: москва
Сообщений: 269
Короче, создаем HashSet, в конструктор передаем исходный массив и вуаля - в HashSet е только уникальные значения
20 июн 15, 22:42    [17798237]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
Изопропил
ZhV
полностью теряется исходная последовательность чисел в массиве

не увидел подобного требования в условиях задачи


В данном случае - да. Это студенческая задача.
Но на эту ему есть классические практические задачи
1) поиск уникальной последовательности максимальной и минимальной длины (M-последовательности) для заданной "большой" последовательности - задача из криптографии

2) поиск авто- и кросс-корреляций в последовательностях - разнообразные аналитические задачи от ядерной физики до фундаментального анализа сток-маркета.


Кстати - попробуйте на досуге "отсортировать" последовательность данных, поступающую со скоростью в десятки мегабайт в секунду. А это вполне нормальный поток для современных спектроанализаторов или томографов.
Хотя... конечно "по жизни" эти задачи решаются не на C#, и даже не на скалярных "процессорах общего назначения".
20 июн 15, 23:04    [17798309]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
eny
Короче, создаем HashSet, в конструктор передаем исходный массив и вуаля - в HashSet е только уникальные значения


Ух ты. То что надо.
Но если я правильно понял - HashSet включает также и неуникальные значения исходной последовательности - но только один раз, поэтому в самом HashSet-е они уникальны.
Наверное, проблему можно решить компаратором, который можно "правильно" нарисовать самому ?
Или сделать исключение HashSet-а из исходной последовательности, а результат (множество) исключить из HashSet-а ?
20 июн 15, 23:37    [17798436]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
ZhV
Member

Откуда:
Сообщений: 198
Дело было вечером... (с)

            int[]  arr = {325,3245,5,54325,5,465326,7,5,214,325, 7} ;

            HashSet<int> hs = new HashSet<int>(arr); // Все значения но по одному разу
            List<int> lst = new List<int>(hs);       // Склонировать в список 

            // исключить из HashSet те, которые в исходном списке больше одного раза
            hs.RemoveWhere(v =>  Array.IndexOf<int>(arr,v) != Array.LastIndexOf<int>(arr,v) );
            //исключить из клон-списка те, которые установлены  в HashSet-е в качестве уникальных значений
            lst.RemoveAll(v => hs.Contains(v));
 //В принципе - все. Можно использовать HashSet и List для дальнейшей обработки

            int[] ar_uniq = new int[hs.Count];
            hs.CopyTo(ar_uniq);                 // Массив уникальных значений
            int[] ar_notuniq = lst.ToArray();   // Массив неуникальных значений

//Визуализация результата
            string s_uniq    = "cnt=" + ar_uniq.Length.ToString();
            string s_notuniq = "cnt=" + ar_notuniq.Length.ToString(); 
             Array.ForEach<int>(ar_uniq, v => s_uniq += " " + v.ToString());
             Array.ForEach<int>(ar_notuniq, v => s_notuniq += " "+ v.ToString());
//    s_uniq = "cnt=4  3245 54325 465326 214"
// s_notuniq = "cnt=3  325 5 7"
21 июн 15, 01:42    [17798757]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Dima T
Member

Откуда:
Сообщений: 11465
ZhV
но число то не уникально в последовательности и условие задачи не выполняется

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

ZhV
Array.Contains работает на "нижайшем уровне" - команды ассемблера scasb или scasw (сканирование области памяти на поиск совпадений) работают очень быстро.

1. Эти команды работают с данными размера 1/2/4 байта, т.е., например, для строки в 10 байт это неприменимо.
2. Если не путаю: C# не гарантирует что массив займет непрерывный кусок памяти.
3. Наивно думать что одна "магическая" команда процессора даст резкий прирос производительности.

Вобщем надо тестить все варианты на скорость и потребление памяти.
21 июн 15, 14:07    [17799185]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
stut
Member

Откуда:
Сообщений: 454
У меня смежный вопрос: было у меня когда то задание на нахождение уникальных элементов в матрице, которое может снова мне попастся. Условие точно не помню. Но надо было найти уникальные элементы (или повторяющее) в стовпцах/строках матрицы. Может в условие бы предусмотрено что количество этих элементов должно быть однаковым в стовпцах. Я тогда брался создавать лист этих элементов, делать траверс по колонке, и потом должен был сравнивать с листом других(ой) колонок но ничего хорошего не вышло из этого - попросту не хватило времени. Можно ли в этом случае применить Set - Hashset (), SortedSet() без переопределение методов hashcode(), equals() (C#). Меня интересует общий подход к решение таких задач когда сперва надо определить некие элементы в колонке, а потом сравнивать с другими столбцами?
20 сен 17, 12:35    [20808562]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 2414
stut
У меня смежный вопрос: было у меня когда то задание на нахождение уникальных элементов в матрице, которое может снова мне попастся. Условие точно не помню. Но надо было найти уникальные элементы (или повторяющее) в стовпцах/строках матрицы. Может в условие бы предусмотрено что количество этих элементов должно быть однаковым в стовпцах. Я тогда брался создавать лист этих элементов, делать траверс по колонке, и потом должен был сравнивать с листом других(ой) колонок но ничего хорошего не вышло из этого - попросту не хватило времени. Можно ли в этом случае применить Set - Hashset (), SortedSet() без переопределение методов hashcode(), equals() (C#). Меня интересует общий подход к решение таких задач когда сперва надо определить некие элементы в колонке, а потом сравнивать с другими столбцами?

Если коротко то:
Для структур и анонимных классов метод GetHashCode() можно не переопределять, он будет работать из коробки.
Если поля структуры или свойства анонимного класса совпадают, то их хеш сумма будет совпадать и они будут эквивалентны. (Если конечно метод не переопределён)
Для классов если метод не переопределен, то используется метод по умолчанию, который возвращает указатель на объект.
Если переопределяете метод GetHashCode, необходимо переопередилть его собрата Equals
любой 2мерный массив можно представить как одномерный
20 сен 17, 13:06    [20808670]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
stut
Member

Откуда:
Сообщений: 454
Задание скорее из элементарного програмирования - манипуляции из 2ерным масивов. Лист принял как динамичный масив, в котором неизвестно заведомо количество элементов. Set должен работать с уникальными элементами - но имеет он методы типа subsetof()/intersectwith(), но специального метода distinct не существует, да и добавление дубликата даже не вызывает исключение кажется.
20 сен 17, 13:54    [20808943]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
stut
Member

Откуда:
Сообщений: 454
Да задание появилось на бис. Вообще условие достаточно простое: найти столбцы матрицы с однаковими сетами (множествами) чисел. Только вот вопрос -- возможно ли это реализировать без колекций List и HashSet? То есть достаточно ли здесь лиш процедурного подхода и масивов?
21 сен 17, 21:14    [20813691]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
stut
Member

Откуда:
Сообщений: 454
Я использовал Лист Хешсетов (чисел типа doublе). Кроме других мелких прорехов сравнивал эти хешсеты выдобутые из листа посредством hashset_a.equals(hashset_b), что наверное неправильно?
21 сен 17, 21:24    [20813717]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
stut
Member

Откуда:
Сообщений: 454
так правильный мой подход в принципе или нет? Правильно ли его применять в этом случае, есть ли он самый простой? Или можно обойтись лиш одними масивами без колекций?
23 сен 17, 15:47    [20818060]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Сон Веры Павловны
Member

Откуда:
Сообщений: 3450
Roman Mejtes
Для классов если метод не переопределен, то используется метод по умолчанию, который возвращает указатель на объект.

Неверно. Подробности, например, здесь.
23 сен 17, 17:02    [20818110]     Ответить | Цитировать Сообщить модератору
 Re: Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый масси  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 1600
ZhV
Dima T
Сортируешь и идешь последовательно, если текущий равен предыдущему - пропускаешь.


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

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


В чем большая разница?
25 сен 17, 11:24    [20820049]     Ответить | Цитировать Сообщить модератору
Все форумы / WinForms, .Net Framework Ответить