Как найти одинаковые элементы одномерного массива - AvtoShod.ru

#статьи

23 янв 2023
0

Задача: проверить массив на дубликаты

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем в массиве повторяющиеся элементы.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Дан массив целых чисел — nums. Необходимо написать функцию, которая возвращает true, если в этом массиве хотя бы одно число повторяется дважды. Если же все элементы уникальны, функция должна вернуть false.


Ввод: nums = [1,2,3,1]
Вывод: true


Ввод: nums = [1,2,3,4]
Вывод: false


Ввод: nums = [1,1,1,3,3,4,3,2,4,2]
Вывод: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

При решении подобных задач важно выбрать подходящий тип данных. Здесь мы исходим из такой логики: «повторяется дважды» → значит, ищем дубликаты. Следовательно, выбираем множество (set).

Мы создадим пустое множество и будем обходить весь массив, просто проверяя, находится ли элемент во множестве:

если он ещё не находится — добавляем его;
если элемент уже там — значит, мы встретили повторяющийся элемент и просто возвращаем true.


public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (set.contains(i)) {
            return true;
        } else {
            set.add(i);
        }
    }
    return false;
}

Результаты

Временная сложность: O(n) — так как в самом плохом случае мы проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Научитесь: Профессия Java-разработчик
Узнать больше

Источник

Задача — найти одинаковые значения в массиве.
Что не так в коде?

void main(void)
{
    int a[5]={1,5,3,4,5},i=0,k;

    for(k=0;k<=4;k++)
    {
        do
        {
            if(a[k]==a[i]){
                printf("%i",a[i]);
            }
            i++;
        }
        while((i-4)==0);
    }
    _getch();
}

angry

8,64717 золотых знаков73 серебряных знака180 бронзовых знаков

задан 6 янв 2012 в 12:59

void main()
{ int a[5]={1,2,3,4,5};
int i=0;k=0;

for (i=0; i<5; i++) {

      for(k=5;k>i;k-1){

        if(a[i]==a[k]){Напечатать сообщение или убить всех человеков;}
     }
  }
}

Смысл в том что программа будет сравнивать 1 элемент со всеми в массиве, затем 2ой элемент со всеми и т.д.

ответ дан 6 янв 2012 в 13:13

BlackOverlordBlackOverlord

6322 золотых знака13 серебряных знаков32 бронзовых знака

Ошибка в этой строке: while((i-4)==0);. Замени её на while(i<5);, а также инициализируй i нулём во внешнем цикле перед do. Ты хоть пробовал сам ошибку искать? Перед тем, как запускать код, надо прокрутить алгоритм у себя в голове. Сразу наткнёшься на то, что в while будет сравниваться -4 с 0, и цикл прекратится.

Исправленный вариант должен работать, но мне он не очень нравится. Зачем мешать разные циклы? Цикл do … while выполняется всегда, как минимум, один раз, независимо от условия. Здесь это не нужно, можно обойтись двумя for, как тебе написали выше.

ответ дан 6 янв 2012 в 15:55

devolndevoln

5,40120 серебряных знаков32 бронзовых знака

Источник

Given an array of n integers. The task is to print the duplicates in the given array. If there are no duplicates then print -1.

Examples:

Input: {2, 10,10, 100, 2, 10, 11,2,11,2}
Output: 2 10 11

Input: {5, 40, 1, 40, 100000, 1, 5, 1}
Output: 5 40 1

Note: The duplicate elements can be printed in any order.

Simple Approach: The idea is to use nested loop and for each element check if the element is present in the array more than once or not. If present, then store it in a Hash-map. Otherwise, continue checking other elements.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void findDuplicates(int arr[], int len)

{

bool ifPresent = false;

vector<int> al;

for(int i = 0; i < len - 1; i++)

{

for(int j = i + 1; j < len; j++)

{

if (arr[i] == arr[j])

{

auto it = std::find(al.begin(),

al.end(), arr[i]);

if (it != al.end())

{

break;

}

else

{

al.push_back(arr[i]);

ifPresent = true;

}

if (ifPresent == true)

{

cout << "[" << al[0] << ", ";

for(int i = 1; i < al.size() - 1; i++)

{

cout << al[i] << ", ";

}

cout << al[al.size() - 1] << "]";

}

else

{

cout << "No duplicates present in arrays";

}

int main()

{

int arr[] = { 12, 11, 40, 12,

5, 6, 5, 12, 11 };

int n = sizeof(arr) / sizeof(arr[0]);

findDuplicates(arr, n);

return 0;

}

Java

import java.util.ArrayList;

public class GFG {

static void findDuplicates(

int arr[], int len)

{

boolean ifPresent = false;

ArrayList<Integer> al = new ArrayList<Integer>();

for (int i = 0; i < len - 1; i++) {

for (int j = i + 1; j < len; j++) {

if (arr[i] == arr[j]) {

if (al.contains(arr[i])) {

break;

}

else {

al.add(arr[i]);

ifPresent = true;

}

if (ifPresent == true) {

System.out.print(al + " ");

}

else {

System.out.print(

"No duplicates present in arrays");

}

public static void main(String[] args)

{

int arr[] = { 12, 11, 40, 12, 5, 6, 5, 12, 11 };

int n = arr.length;

findDuplicates(arr, n);

}

Python3

def findDuplicates(arr, Len):

ifPresent = False

a1 = []

for i in range(Len - 1):

for j in range(i + 1, Len):

if (arr[i] == arr[j]):

if arr[i] in a1:

break

else:

a1.append(arr[i])

ifPresent = True

if (ifPresent):

print(a1, end = " ")

else:

print("No duplicates present in arrays")

arr = [ 12, 11, 40, 12, 5, 6, 5, 12, 11 ]

n = len(arr)

findDuplicates(arr, n)

C#

using System;

using System.Collections.Generic;

class GFG{

static void findDuplicates(int[] arr, int len)

{

bool ifPresent = false;

List<int> al = new List<int>();

for(int i = 0; i < len - 1; i++)

{

for(int j = i + 1; j < len; j++)

{

if (arr[i] == arr[j])

{

if (al.Contains(arr[i]))

{

break;

}

else

{

al.Add(arr[i]);

ifPresent = true;

}

if (ifPresent == true)

{

Console.Write("[" + al[0] + ", ");

for(int i = 1; i < al.Count - 1; i++)

{

Console.Write(al[i] + ", ");

}

Console.Write(al[al.Count - 1] + "]");

}

else

{

Console.Write("No duplicates present in arrays");

}

static void Main()

{

int[] arr = { 12, 11, 40, 12,

5, 6, 5, 12, 11 };

int n = arr.Length;

findDuplicates(arr, n);

}

Javascript

<script>

function findDuplicates(arr, len) {

let ifPresent = false;

let al = new Array();

for (let i = 0; i < len - 1; i++) {

for (let j = i + 1; j < len; j++) {

if (arr[i] == arr[j]) {

if (al.includes(arr[i])) {

break;

}

else {

al.push(arr[i]);

ifPresent = true;

}

if (ifPresent == true) {

document.write(`[${al}]`);

}

else {

document.write("No duplicates present in arrays");

}

let arr = [12, 11, 40, 12, 5, 6, 5, 12, 11];

let n = arr.length;

findDuplicates(arr, n);

</script>

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: Use unordered_map for hashing. Count frequency of occurrence of each element and the elements with frequency more than 1 is printed. unordered_map is used as range of integers is not known. For Python, Use Dictionary to store number as key and it’s frequency as value. Dictionary can be used as range of integers is not known.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printDuplicates(int arr[], int n)

{

    unordered_map<int, int> freq;

    for (int i=0; i<n; i++)

        freq[arr[i]]++;

    bool dup = false;

    unordered_map<int, int>:: iterator itr;

    for (itr=freq.begin(); itr!=freq.end(); itr++)

    {

        if (itr->second > 1)

        {

            cout << itr->first << " ";

            dup = true;

        }

    }

    if (dup == false)

        cout << "-1";

}

int main()

{

    int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    printDuplicates(arr, n);

    return 0;

}

Java

import java.util.HashMap;

import java.util.Map;

import java.util.Map.Entry;

public class FindDuplicatedInArray

{

    public static void main(String[] args)

    {

        int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};

        int n = arr.length;

        printDuplicates(arr, n);

    }

    private static void printDuplicates(int[] arr, int n)

    {

        Map<Integer,Integer> map = new HashMap<>();

        int count = 0;

        boolean dup = false;

        for(int i = 0; i < n; i++){

            if(map.containsKey(arr[i])){

                count = map.get(arr[i]);

                map.put(arr[i], count + 1);

            }

            else{

                map.put(arr[i], 1);

            }

        }

        for(Entry<Integer,Integer> entry : map.entrySet())

        {

            if(entry.getValue() > 1){

                System.out.print(entry.getKey()+ " ");

                dup = true;

            }

        }

        if(!dup){

            System.out.println("-1");

        }

    }

}

Python3

def printDuplicates(arr):

    dict = {}

    for ele in arr:

        try:

            dict[ele] += 1

        except:

            dict[ele] = 1

    for item in dict:

        if(dict[item] > 1):

            print(item, end=" ")

    print("n")

if __name__ == "__main__":

    list = [12, 11, 40, 12,

            5, 6, 5, 12, 11]

    printDuplicates(list)

C#

using System;

using System.Collections.Generic;

class GFG

{

    static void printDuplicates(int[] arr, int n)

    {

        Dictionary<int,

                   int> map = new Dictionary<int,

                                             int>();

        int count = 0;

        bool dup = false;

        for (int i = 0; i < n; i++)

        {

            if (map.ContainsKey(arr[i]))

            {

                count = map[arr[i]];

                map[arr[i]]++;

            }

            else

                map.Add(arr[i], 1);

        }

        foreach (KeyValuePair<int,

                              int> entry in map)

        {

            if (entry.Value > 1)

                Console.Write(entry.Key + " ");

            dup = true;

        }

        if (!dup)

            Console.WriteLine("-1");

    }

    public static void Main(String[] args)

    {

        int[] arr = { 12, 11, 40, 12,

                     5, 6, 5, 12, 11 };

        int n = arr.Length;

        printDuplicates(arr, n);

    }

}

Javascript

<script>

function printDuplicates(arr, n)

{

    var freq = new Map();

    for(let i = 0; i < n; i++)

    {

        if (freq.has(arr[i]))

        {

            freq.set(arr[i], freq.get(arr[i]) + 1);

        }

        else

        {

            freq.set(arr[i], 1);

        }

    }

    var dup = false;

    for(let [key, value] of freq)

    {

        if (value > 1)

        {

            document.write(key + " ");

            dup = true;

        }

    }

    if (dup == false)

        document.write("-1");

}

var arr = [ 12, 11, 40, 12,

            5, 6, 5, 12, 11 ];

var n = arr.length;

printDuplicates(arr, n);

</script>

Time Complexity: O(N)
Auxiliary Space: O(N)

Another Efficient Approach(Space optimization):

First we will sort the array for binary search function.
we will find index at which arr[i] occur first time lower_bound
Then , we will find index at which arr[i] occur last time upper_bound
Then check if diff=(last_index-first_index+1)>1
If diff >1 means it occurs more than once and print

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printDuplicates(int arr[], int n)

{

sort(arr,arr+n);

cout<<"[";

for(int i = 0 ; i < n ;i++)

{

int first_index = lower_bound(arr,arr+n,arr[i])- arr;

int last_index = upper_bound(arr,arr+n,arr[i])- arr-1;

int occur_time = last_index-first_index+1;

if(occur_time > 1 )

{ i=last_index;

cout<<arr[i]<<", "; }

} cout<<"]";

}

int main()

{ int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};

int n = sizeof(arr) / sizeof(arr[0]);

printDuplicates(arr, n);

return 0;

}

Python3

def printDuplicates(arr, n):

arr.sort()

print("[", end="")

i = 0

while i < n:

first_index = arr.index(arr[i])

last_index = n - arr[::-1].index(arr[i]) - 1

occur_time = last_index - first_index + 1

if occur_time > 1:

i = last_index

print(arr[i], end=", ")

i += 1

print("]")

arr = [12, 11, 40, 12, 5, 6, 5, 12, 11]

n = len(arr)

printDuplicates(arr, n)

Java

import java.io.*;

import java.util.*;

class GFG {

public static int lowerBound(int[] arr, int target)

{

int lo = 0, hi = arr.length - 1;

int ans = -1;

while (lo <= hi) {

int mid = lo + (hi - lo) / 2;

if (arr[mid] >= target) {

ans = mid;

hi = mid - 1;

}

else {

lo = mid + 1;

}

return ans;

}

public static int upperBound(int[] arr, int target)

{

int lo = 0, hi = arr.length - 1;

int ans = -1;

while (lo <= hi) {

int mid = lo + (hi - lo) / 2;

if (arr[mid] <= target) {

ans = mid;

lo = mid + 1;

}

else {

hi = mid - 1;

}

return ans;

}

static void printDuplicates(int[] arr, int n)

{

Arrays.sort(arr);

System.out.print("[");

for (int i = 0; i < n; i++) {

int firstIndex = lowerBound(arr, arr[i]);

int lastIndex = upperBound(arr, arr[i]);

int occurTime = lastIndex - firstIndex

+ 1;

if (occurTime

> 1) {

i = lastIndex;

System.out.print(arr[i] + ", ");

}

System.out.println("]");

}

public static void main(String[] args)

{

int[] arr = { 12, 11, 40, 12, 5, 6, 5, 12, 11 };

int n = arr.length;

printDuplicates(arr, n);

}

Javascript

function printDuplicates(arr, n) {

arr.sort();

console.log("[");

for (let i = 0; i < n; i++)

{

let first_index = arr.indexOf(arr[i]);

let last_index = arr.lastIndexOf(arr[i]);

let occur_time = last_index - first_index + 1;

if (occur_time > 1) {

i = last_index;

console.log(arr[i] + ", ");

}

console.log("]");

}

let arr = [12, 11, 40, 12, 5, 6, 5, 12, 11];

let n = arr.length;

printDuplicates(arr, n);

C#

using System;

class MainClass {

static void printDuplicates(int[] arr, int n) {

Array.Sort(arr);

Console.Write("[");

for (int i = 0; i < n; i++) {

int first_index = Array.IndexOf(arr, arr[i]);

int last_index = Array.LastIndexOf(arr, arr[i]);

int occur_time = last_index - first_index + 1;

if (occur_time > 1) {

i = last_index;

Console.Write(arr[i] + ", ");

}

Console.Write("]");

}

static void Main() {

int[] arr = {12, 11, 40, 12, 5, 6, 5, 12, 11};

int n = arr.Length;

printDuplicates(arr, n);

}

Time Complexity: O(n*log₂n)
Auxiliary Space: O(1)

Related Post :
Print All Distinct Elements of a given integer array
Find duplicates in O(n) time and O(1) extra space | Set 1
Duplicates in an array in O(n) and by using O(1) extra space | Set-2
Print all the duplicates in the input string

This article is contributed by Ayush Jauhari. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Last Updated :
18 Apr, 2023

Like Article

Save Article

Источник

LookLand

0 / 0 / 0

Регистрация: 06.09.2010

Сообщений: 45

Поиск одинаковых элементов в одномерном массиве

15.05.2013, 23:50. Показов 24743. Ответов 3

Метки нет (Все метки)

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

C++

#include <iostream>
#include <Windows.h>
 
using namespace std;
 
int main()
    {
    setlocale (LC_ALL, "Russian_Russia.1251");
    int a[10];
    cout << "Введите числа массива" << endl;
 
    for(int i = 0; i<=10; i++)
    {
        cout << "a" << "[" << i << "] = ";
        cin >> a[i];
    }
 
    int n = 0;
    int l = 0;
    for(int j = 0; j <=11; j++)
    {
 
        n++;
 
 
        for(int i = n; i<=10; i++)
 
            if(a[j] == a[i])
                {
                 l++;
                }
 
            cout << l << endl; // для проверки точности
 
    }
 
 
 
 
 
 
    }

MyMind

25 / 25 / 35

Регистрация: 14.05.2013

Сообщений: 68

15.05.2013, 23:59

созданный вами массив размерностью 10, а с клавиатуры по вашему первому фору вы вводите 11 элементов.

Добавлено через 4 минуты
попробуйте так:

C++

#include <iostream>
#include <conio.h>
 
using namespace std;
 
int main() {
    setlocale (LC_ALL, "Russian_Russia.1251");
    int a[10];
    cout << "Введите числа массива" << endl; 
    for(int i = 0; i<10; i++) {
        cout << "a" << "[" << i << "] = ";
        cin >> a[i];
    }
    int l = 0;
    for(int j = 0; j < 9; j++)  
        for(int i = j+1; i < 10; i++) 
            if(a[j] == a[i]) l++;
     cout << l << endl; // для проверки точности
     getch();
 }

Sergei066800

1 / 1 / 0

Регистрация: 30.09.2012

Сообщений: 8

16.05.2013, 02:04

C++

#include <iostream>
#include <conio.h> 
using namespace std;
int main()
    {
    setlocale (LC_ALL, "Russian_Russia.1251");
    int a[10], n = 0, l = 0;
    cout << "Введите числа массива" << endl;
    for(int i = 0; i<=9; i++)
    {
        cout << "a" << "[" << i << "] = ";
        cin >> a[i];
    }
   
    for(int j = 0; j <=9; j++)
    {
        n++;
        for(int i = n; i<=9; i++)
            if(a[j] == a[i]) l++;
    }
    cout << l << endl; // для проверки точности
  getch(); 
    return 0;
    }

Зачем библиотека «#include <Windows.h>»

0 / 0 / 0

Регистрация: 06.09.2010

Сообщений: 45

16.05.2013, 23:09

[ТС]

Разобрался. Всем спасибо.

Источник

В этом посте мы обсудим, как проверить наличие дубликатов в массиве на C++.

1. Использование набора

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

#include <iostream>

#include <unordered_set>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::unordered_set<int> distinct(std::begin(arr), std::end(arr));

bool hasDuplicates = n != distinct.size();

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

2. Использование сортировки

Другой вариант — отсортировать массив и сравнить каждую пару последовательных элементов, чтобы проверить наличие дубликатов. Это работает в O(nlog(n)) время, если используется стандартный алгоритм сортировки. Это будет переведено в следующий код:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

bool hasDuplicates = false;

std::sort(std::begin(arr), std::end(arr));

for (int i = 0; i < n — 1; i++) {

if (arr[i] == arr[i + 1]) {

hasDuplicates = true;

}

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

3. Использование `std::adjacent_find`

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

#include <iostream>

#include <algorithm>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::sort(arr, arr + n);

bool hasDuplicates = std::adjacent_find(arr, arr + n) != arr + n;

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

С C++11 мы можем получить итератор в начало и конец массива:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

std::sort(std::begin(arr), std::end(arr));

bool hasDuplicates = std::adjacent_find(std::begin(arr), std::end(arr)) != std::end(arr);

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

4. Использование `std::unique` функция

В качестве альтернативы мы можем использовать std::unique функция для удаления последовательных дубликатов после сортировки массива. Его можно использовать следующим образом:

#include <iostream>

#include <algorithm>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::sort(arr, arr + n);

bool hasDuplicates = std::unique(arr, arr + n) != arr + n;

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

С C++11 мы можем получить итератор в начало и конец массива:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

std::sort(std::begin(arr), std::end(arr));

bool hasDuplicates = std::unique(std::begin(arr), std::end(arr)) != std::end(arr);

if (hasDuplicates) {

std::cout << «Array contains duplicates»;

} else {

std::cout << «Array contains no duplicates»;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

Это все о проверке дубликатов в массиве на C++.

Источник

Задача: проверить массив на дубликаты

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Python3

Java

Javascript

C#

Поиск одинаковых элементов в одномерном массиве

1. Использование набора

2. Использование сортировки

3. Использование std::adjacent_find

4. Использование std::unique функция

Не пропустите также:

3. Использование `std::adjacent_find`

4. Использование `std::unique` функция