Given an array of integers of size N, the task is to find the first non-repeating element in this array.
Examples:
Input: {-1, 2, -1, 3, 0}
Output: 2
Explanation: The first number that does not repeat is : 2Input: {9, 4, 9, 6, 7, 4}
Output: 6
Find first non-repeating element in a given Array of integers using Nested Loops:
This approach is based on the following idea:
Simple Solution is to use two loops. The outer loop picks elements one by one and the inner loop checks if the element is present more than once or not..
Illustration:
Given arr[] = {-1, 2, -1, 3, 0}
For element at i = 0:
- The value of element at index 2 is same, then this can’t be first non-repeating element
For element at i = 1:
- After traversing the array arr[1] is not present is not present in the array except at 1.
Hence, element is index 1 is the first non-repeating element which is 2
Follow the steps below to solve the given problem:
- Loop over the array from the left.
- Check for each element if its presence is present in the array for more than 1 time.
- Use a nested loop to check the presence.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
int firstNonRepeating(int arr[], int n)
{
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < n; j++)
if (i != j && arr[i] == arr[j])
break;
if (j == n)
return arr[i];
}
return -1;
}
int main()
{
int arr[] = { 9, 4, 9, 6, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << firstNonRepeating(arr, n);
return 0;
}
Java
class GFG {
static int firstNonRepeating(int arr[], int n)
{
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < n; j++)
if (i != j && arr[i] == arr[j])
break;
if (j == n)
return arr[i];
}
return -1;
}
public static void main(String[] args)
{
int arr[] = { 9, 4, 9, 6, 7, 4 };
int n = arr.length;
System.out.print(firstNonRepeating(arr, n));
}
}
Python3
def firstNonRepeating(arr, n):
for i in range(n):
j = 0
while(j < n):
if (i != j and arr[i] == arr[j]):
break
j += 1
if (j == n):
return arr[i]
return -1
arr = [9, 4, 9, 6, 7, 4]
n = len(arr)
print(firstNonRepeating(arr, n))
C#
using System;
class GFG {
static int firstNonRepeating(int[] arr, int n)
{
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < n; j++)
if (i != j && arr[i] == arr[j])
break;
if (j == n)
return arr[i];
}
return -1;
}
public static void Main()
{
int[] arr = { 9, 4, 9, 6, 7, 4 };
int n = arr.Length;
Console.Write(firstNonRepeating(arr, n));
}
}
PHP
<?php
function firstNonRepeating($arr, $n)
{
for ($i = 0; $i < $n; $i++)
{
$j;
for ($j = 0; $j< $n; $j++)
if ($i != $j && $arr[$i] == $arr[$j])
break;
if ($j == $n)
return $arr[$i];
}
return -1;
}
$arr = array(9, 4, 9, 6, 7, 4);
$n = sizeof($arr) ;
echo firstNonRepeating($arr, $n);
?>
JavaScript
<script>
function firstNonRepeating(arr, n) {
for (let i = 0; i < n; i++) {
let j;
for (j = 0; j < n; j++)
if (i != j && arr[i] == arr[j])
break;
if (j == n)
return arr[i];
}
return -1;
}
let arr = [9, 4, 9, 6, 7, 4];
let n = arr.length;
document.write(firstNonRepeating(arr, n));
</script>
Time Complexity: O(n*n), Checking for each element n times
Auxiliary Space: O(1)
Find first non-repeating element in a given Array of integers using Hashing:
This approach is based on the following idea:
- The idea is to store the frequency of every element in the hashmap.
- Then check the first element whose frequency is 1 in the hashmap.
- This can be achieved using hashing
Illustration:
arr[] = {-1, 2, -1, 3, 0}
Frequency map for arr:
- -1 -> 2
- 2 -> 1
- 3 -> 1
- 0 -> 1
Traverse arr[] from left:
At i = 0:
- Frequency of arr[0] is 2, therefore it can’t be first non-repeating element
At i = 1:
- Frequency of arr[1] is 1, therefore it will be the first non-repeating element.
Hence, 2 is the first non-repeating element.
Follow the steps below to solve the given problem:
- Traverse array and insert elements and their counts in the hash table.
- Traverse array again and print the first element with a count equal to 1.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
int firstNonRepeating(int arr[], int n)
{
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
for (int i = 0; i < n; i++)
if (mp[arr[i]] == 1)
return arr[i];
return -1;
}
int main()
{
int arr[] = { 9, 4, 9, 6, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << firstNonRepeating(arr, n);
return 0;
}
Java
import java.util.*;
class GFG {
static int firstNonRepeating(int arr[], int n)
{
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < n; i++) {
if (m.containsKey(arr[i])) {
m.put(arr[i], m.get(arr[i]) + 1);
}
else {
m.put(arr[i], 1);
}
}
for (int i = 0; i < n; i++)
if (m.get(arr[i]) == 1)
return arr[i];
return -1;
}
public static void main(String[] args)
{
int arr[] = { 9, 4, 9, 6, 7, 4 };
int n = arr.length;
System.out.println(firstNonRepeating(arr, n));
}
}
Python3
from collections import defaultdict
def firstNonRepeating(arr, n):
mp = defaultdict(lambda: 0)
for i in range(n):
mp[arr[i]] += 1
for i in range(n):
if mp[arr[i]] == 1:
return arr[i]
return -1
arr = [9, 4, 9, 6, 7, 4]
n = len(arr)
print(firstNonRepeating(arr, n))
C#
using System;
using System.Collections.Generic;
class GFG {
static int firstNonRepeating(int[] arr, int n)
{
Dictionary<int, int> m = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (m.ContainsKey(arr[i])) {
var val = m[arr[i]];
m.Remove(arr[i]);
m.Add(arr[i], val + 1);
}
else {
m.Add(arr[i], 1);
}
}
for (int i = 0; i < n; i++)
if (m[arr[i]] == 1)
return arr[i];
return -1;
}
public static void Main(String[] args)
{
int[] arr = { 9, 4, 9, 6, 7, 4 };
int n = arr.Length;
Console.WriteLine(firstNonRepeating(arr, n));
}
}
Javascript
<script>
function firstNonRepeating(arr , n)
{
const m = new Map();
for (var i = 0; i < n; i++) {
if (m.has(arr[i])) {
m.set(arr[i], m.get(arr[i]) + 1);
}
else {
m.set(arr[i], 1);
}
}
for (var i = 0; i < n; i++)
if (m.get(arr[i]) == 1)
return arr[i];
return -1;
}
var arr = [ 9, 4, 9, 6, 7, 4 ];
var n = arr.length;
document.write(firstNonRepeating(arr, n));
</script>
Time Complexity: O(2n), Traverse over the array to map the frequency and again traverse over the array to check for frequency.
Auxiliary Space: O(n), Create a hash table for storing frequency
Another Approach using dictionary:
Step 1: Create a dictionary
Step 2: Store all the elements frequency.
Step 3: Run another loop to check whose frequency is equal to 1.
Step 4: Return the element.
C++
#include <iostream>
#include <unordered_map>
using namespace std;
int firstNonRepeating(int arr[], int n) {
unordered_map<int, int> dic;
for (int i = 0; i < n; i++) {
dic[arr[i]]++;
}
for (int i = 0; i < n; i++) {
if (dic[arr[i]] == 1) {
return arr[i];
}
}
return -1;
}
int main() {
int arr[] = {9, 4, 9, 6, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int result = firstNonRepeating(arr, n);
if (result != -1) {
cout << "The first non-repeating element is: " << result << endl;
} else {
cout << "There is no non-repeating element in the array." << endl;
}
return 0;
}
Java
import java.util.*;
public class Main {
public static int firstNonRepeating(int[] arr, int n)
{
Map<Integer, Integer> freq
= new HashMap<Integer, Integer>();
for (int i : arr) {
freq.put(i, freq.getOrDefault(i, 0) + 1);
}
for (int i : arr) {
if (freq.get(i) == 1) {
return i;
}
}
return -1;
}
public static void main(String[] args)
{
int[] arr = { 9, 4, 9, 6, 7, 4 };
int n = arr.length;
System.out.println(firstNonRepeating(arr, n));
}
}
Python3
def firstNonRepeating(arr, n):
dic={}
for i in arr:
dic[i]=0
for i in arr:
dic[i] +=1
for i in arr:
if dic[i] ==1:
return i
arr = [9, 4, 9, 6, 7, 4]
n = len(arr)
print(firstNonRepeating(arr, n))
C#
using System;
using System.Collections.Generic;
class MainClass {
public static int firstNonRepeating(int[] arr, int n) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int i in arr) {
if (freq.ContainsKey(i)) {
freq[i]++;
} else {
freq.Add(i, 1);
}
}
foreach (int i in arr) {
if (freq[i] == 1) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
int[] arr = { 9, 4, 9, 6, 7, 4 };
int n = arr.Length;
Console.WriteLine(firstNonRepeating(arr, n));
}
}
Javascript
function firstNonRepeating(arr, n) {
let dic = {};
for (let i of arr) {
dic[i] = 0;
}
for (let i of arr) {
dic[i] += 1;
}
for (let i of arr) {
if (dic[i] == 1) {
return i;
}
}
}
let arr = [9, 4, 9, 6, 7, 4];
let n = arr.length;
console.log(firstNonRepeating(arr, n));
Time Complexity: O(N).
Auxiliary Space: O(N).
Last Updated :
04 Apr, 2023
Like Article
Save Article
Перейти к содержанию
Вывести неповторяющиеся элементы массива
Просмотров 6.1к. Обновлено 15 октября 2021
В массиве найти элементы, которые в нем встречаются только один раз, и вывести их на экран. То есть найти и вывести уникальные элементы массива.
Будем брать очередной элемент массива и сравнивать его со всеми остальными элементами массива от начала до конца. Если при сравнении два элемента окажутся равны друг другу, и при этом элемент не сравнивается сам с собой, то значит этот «исследуемый» элемент не уникальный. Дальнейшее сравнение этого элемента не имеет смысла, и надо перейти к следующему. Если же ни одного совпадения не было найдено, значит элемент не повторяется в массиве, и его надо вывести на экран.
В программе можно использовать переменную-флаг. Перед началом проверки уникальности элемента присвоить ей, например, значение 1. Если совпадение будет найдено, то присвоить флагу 0. Если же после всех сравнений флаг остался равен 1, то значит элемент массива не повторяется в нем.
Pascal
уникальные элементы массива паскаль
const N = 20;
var
a: array[1..N] of word;
i,j: byte;
flag: boolean;
begin
randomize;
for i:=1 to N do begin
a[i] := random(15);
write(a[i],' ');
end;
writeln;
for i:=1 to N do begin
flag := True;
for j:=1 to N do
if (a[i] = a[j]) and (j <> i) then begin
flag := False;
break;
end;
if flag = True then
write(a[i],' ');
end;
writeln
end.
12 5 7 6 5 13 5 1 1 14 1 3 13 4 13 4 3 9 11 9
12 7 6 14 11
Язык Си
уникальные элементы массива c++
#include
#define N 20
main() {
unsigned short a[N], i, j, f;
srand(time(NULL));
for (i=0; i< N; i++) {
a[i] = rand() % 15;
printf("%d ", a[i]);
}
printf("n");
for (i=0; i< N; i++) {
f = 1;
for (j=0; j< N; j++)
if (a[i] == a[j] && i != j) {
f = 0;
break;
}
if (f == 1) printf("%d ", a[i]);
}
printf("n");
}
7 9 5 11 1 11 10 11 5 14 10 9 6 14 6 13 6 11 0 9
7 1 13 0
Python
уникальные элементы массива Python (питон)
from random import random
N = 20
a = [0] * N
for i in range(N):
a[i] = int(random()*15)
print(a[i],end=' ')
print()
for i in range(N):
f = True
for j in range(N):
if a[i] == a[j] and i != j:
f = False
break
if f == True:
print(a[i],end=' ')
print()
1 3 2 8 12 6 10 6 13 11 6 4 10 9 2 8 7 13 1 9
3 12 11 4 7
Basic-256
N = 20
dim a(N)
for i=0 to N-1
a[i] = int(rand * 15)
print a[i] + " ";
next i
for i=0 to N-1
f = 1
for j=0 to N-1
if a[i] = a[j] and i <> j then
f = 0
endif
next j
if f = 1 then print a[i] + " ";
next i
12 1 8 10 14 3 7 1 14 5 5 2 14 13 3 9 14 10 12 11
8 7 2 13 9 11
Сегодня разберем одно из заданий, часто ставящее в тупик еще на этапе условия. Разберем как вывести неповторяющиеся элементы массива и напишем программу на языке C++.
Если описать задание немного более простым языком, то нам всего лишь нужно найти и вывести элементы массива, значения которых встречаются один раз. Проще говоря — уникальные значения элементов массива.
Имея массив [1, 3, 5, 8, 3, 8], мы должны вывести 1, 5. Почему? Потому что 3 и 8 встречаются в массиве больше одного раза.
Решений может быть несколько, давайте разберем самое простое. Мы будем брать каждый элемент массива и сравнивать его со всеми остальными, если совпадений не найдется, то мы просто его выводим и идем дальше.
Звучит довольно просто, но на деле нам понадобится цикл в цикле. Первым циклом будем проходить по всем элементам массива, а второй нужен будет для поиска совпадений.
Давайте реализуем алгоритм для вывода неповторяющихся элементов массива на C++
#include
using namespace std;
int main()
{
/* Заполним массив значениями */
int n = 6;
int mass[n] = {1, 3, 5, 8, 3, 8};
/* Проходим по всем элементам массива */
for (int i = 0; i < n; ++i) {
// Вынесем текущий элемент в переменную
int currentElementValue = mass[i];
// Имеет ли текущий элемент значение, встречающееся в массиве
// по умолчанию нет
bool hasEquals = false;
/* Берем элемент и ищем по массиву такое же значение */
for (int r = 0; r < n; ++r) {
// С самим с собой не сравниваем, пропускаем итерацию
if (i == r) {
continue;
}
// Если текущий элемент равен другому элементу
if (currentElementValue == mass[r] && i != r) {
// То устанавливаем флаг, что такое значение встречалось
hasEquals = true;
}
}
// Если у этого элемента нет встречающихся значений, то выводим
if (!hasEquals) {
cout << currentElementValue << " ";
}
}
return 0;
}
В программе я использовал такой же массив, котрый описал в условии. Компилируем, запускаем и видим вывод
1 5
То есть то, что необходимо.
Постановка задачи:
Массив из n =2k+2 элементов, 2 элемента не имеют пары, остальные парные. Найти эти 2 элемента, при условии, что алгоритм должен работать за O(n) времени и использовать O(1) дополнительной памяти.
Решение для поиска одного не повторяющего элемента:
Сначала рассмотрим задачу, когда один элемент различен. Вспомним свойство xor, применение к 2 одинаковым числа даст ноль. Следовательно если мы пропустим весь массив, то в результате у нас останется как раз искомый элемент.
int mas[] = {4,5,23,7,7,23,4,5,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
ans ^= mas[i];
}
System.out.print(ans);
Решение для поиска 2 не повторяющихся элементов:
Для поиска двух элементов мы делаем сначала аналогично первому варианту, но теперь у нас в ответе пока находится xor этих двух чисел. Но если в бите установлена 1 значит в одном числе она есть, а во втором ее нет. Поэтому найдем также xor для все чисел которые имееют бит 1 в этом разряде. А второе число находится исходя из свойства xor.
int mas[] = {4,5,23,7,7,23,4,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
ans ^= mas[i];
}
int tmp = 1;
Находим первый разряд в котором есть 1
while ((ans & tmp) == 0) {
tmp *= 2;
}
int res = 0;
Находим xor для всех элементов у которых этот бит установлен в 1
for (int i = 0; i < mas.length; i++) {
if ((mas[i] & tmp) > 0) {
res ^= mas[i];
}
}
System.out.println(res);
System.out.println(res ^ ans);
В этой статье затронем один из самых популярных поисковых запросов среди junior-разработчиков: “Как убрать дублирующиеся значения из массива в Javascript”.
Я расскажу про самые популярные способы и распишу их плюсы и минусы.
Конечно же, в каждом из предложенных решений, код можно будет сократить и упростить, но я оставлю его как есть в образовательных целях.
Представим, что у нас есть массив вида:
[1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined]
Теперь попробуем удалить из него дубликаты.
Используем Set
Set – это новый тип данных, представленный в ES6.
Значения Set могут присутствовать только в одном экземпляре, тем самым этот тип данных подразумевает наличие только уникальных элементов.
Соответственно, если мы передадим Array в Set, то мы получим объект только с уникальными значениями.
Перейдем к коду:
const array = [1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined];
const makeUniq = (arr) => {
const uniqSet = new Set(arr);
return [...uniqSet];
}
makeUniq(array);
- Первое, что необходимо сделать – это передать массив в сет.
- Второе – используя spread оператор, преобразовать сет обратно в массив. Так же spread можно заменить на
Array.from(uniqSet).
Теперь давайте максимально укоротим код для того, чтобы оценить количество строк.
const array = [1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined];
const makeUniq = (arr) => [...new Set(arr)];
makeUniq(array);
Плюсы:
- Производительность. Этот вариант самый производительный.
Согласно нотации Big O, сложность алгоритма будет равна O(2n), что в действительности является O(n), а значит производительность максимальная. - Краткость. Самая короткая запись из всех возможных вариантов.
Минусы:
- Обработка только примитивных типов данных. Данный способ не работает, если в массиве будут присутствовать объекты.
Используем filter
Второй вариант удаления – это использование методов массивов .filter() и .indexOf(). Рассмотрим, что делает каждый из них.
Что такое indexOf
Метод .indexOf() возвращает индекс первого, найденного элемента из массива.
Например:
const array = [1, 2, 3, 1, 2, 3, 4];
array.indexOf(1) // 0
array.indexOf(2) // 1
array.indexOf(3) // 2
array.indexOf(4) // 6
Что такое filter
Метод .filter() создаёт новый массив со всеми элементами, прошедшими проверку, задаваемую в передаваемой функции.
Другими словами, если элемент проходит условие и возвращает true, тогда он будет включен в новый массив, непрошедшие элементы будут пропущены.
Решение, используя filter
После того, как вы узнали о .filter() и .indexOf(), перейдем к коду:
const array = [1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined];
const makeUniq = (arr) => {
return arr.filter((el, id) => arr.indexOf(el) === id);
}
makeUniq(array);
Все что необходимо сделать, это перебрать каждое значение массива и сравнить, равен ли индекс первого значения,
текущему, если да, то добавляем значение в новый массив.
Если мы заглянем внутрь arr.filter((el, id) => arr.indexOf(el) === id);, то там происходит примерно это:
| Элемент | Индекс элемента | indexOf | Соответствие условию indexOf(el) === id |
|---|---|---|---|
| 1 | 0 | 0 | true |
| 2 | 1 | 1 | true |
| 3 | 2 | 2 | true |
| 1 | 3 | 0 | false |
| 1 | 4 | 0 | false |
| ‘1’ | 5 | 5 | true |
И так далее с каждым элементом.
Плюсы:
- Популярность. Метод фильтр знаком огромному количеству разработчиков, соответственно, написать решение используя
.filter()очень просто. - Возможность расширить логику для того, чтобы проверять уникальность объектов и массивов.
В данном случае мы можем включить в условие более сложную логику, которая будет проверять на уникальность вложенные массивы и объекты.
Минусы:
- Производительность. В данном случае у нас используется цикл в цикле, т.е. первый цикл это
.filter(), а второй.indexOf(), соответственно сложность алгоритма O(n^2), это значительно медленнее, чем первый вариант.
Если вам необходимо очистить массив с большим количеством элементов, то я не рекомендую использовать данный подход.
Используем reduce
На самом деле, использование .reduce() не принесет вам никакой выгоды, по сравнению с .filter(), просто немного другая логика.
const array = [1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined];
const makeUniq = (arr) => {
return arr.reduce((acc, currentValue) => {
acc.indexOf(currentValue) === -1 && acc.push(currentValue);
return acc;
} , []);
}
makeUniq(array);
В итоге, мы имеем такие же проблемы с производительностью, т.к. используется цикл в цикле – .reduce() и .indexOf() соответственно.
В дополнение к этому, не все разработчики могут быть знакомы с .reduce(). Не самый лучший способ для решения задачи.
Используем цикл for
В случае, если вам необходима производительность, то лучшим решением, по сравнению с .filter() и .reduce() будет обычный цикл for.
- Во-первых, сам
forбыстрее, чем все ES6 методы массивов. - Во-вторых, вы можете написать O(n) решение, вместо O(n^2).
- В-третьих, расширить логику на проверку уникальности вложенных массивов и объектов будет так же просто, как в
.filter()и.reduce().
const array = [1, 2, 3, 1, 1, '1', '2', '1', true, false, true, null, undefined, null, null, undefined];
const makeUniq = (arr) => {
const seen = {};
const result = [];
let j = 0;
for(let i = 0; i < arr.length; i++) {
const item = arr[i];
const itemType = typeof item;
const key = `${itemType}_${item}`;
if (!seen[key]) {
seen[key] = 1;
result[j++] = item;
}
}
return result;
}
makeUniq(array);
Давайте теперь разберемся, что здесь вообще происходит.
- Обозначаем hashtable
const seen = {}, в который будем записывать все значения массива, что мы встретили. - Обозначаем массив, в который будем записывать только уникальные значения.
const result = []. - Обозначем переменную
let j = 0, которая будет использована для быстрой записи значений в массивresult. - Запускаем цикл
forдля полученного массива. - Для уменьшения количества обращений к массиву, создаем константу
const item = arr[i]. - При записи элемента в hashtable в качестве ключа, он будет преобразован в строку, поэтому узнаем его тип и создаем ключ вида type_value
- Проверяем наличие значения в hashtable, если значения нет, то проваливаемся внутрь условия.
- Так как в hashtable не нашлось искомое значение, то записываем его.
- Опять же, так как в hastable не нашлось искомое значение, значит его можно считать уникальным и нужно поместить в массив результатов.
Для этого можно воспользоваться методомarray.push(), но его сложность будет O(n), а присвоить значение напрямую через индекс – O(1), поэтому испольуем индекс.
Плюсы
- Производительность. Согласно Big O нотации, сложность алгоритма будет O(n), производительность максимальная.
- Возможность расширить логику для того, чтобы проверять уникальность объектов и массивов.
Минусы
- Количество кода. По сравнению с любым из предложенных способов, данный имеет самую длинную запись.
- Императивный способ. Еще один минус в читаемости данного подхода, декларативный читается лучше.
Заключение
В этой статье я рассмотрел несколько способов для удаления дублирующихся значений из массивов.
Есть еще варианты, например, написать через .forEach() или через прототип массива, но в целом, они мало отличаются от предложенных.
Главным критерием в выборе подхода, для вас должен стать набор входных данных, если вы имеете дело с огромным количеством значений, то лучше позаботиться о производительности, в остальных случаях я бы предпочел более короткую и читаемую запись.
Ссылки
Мой канал о javascript и веб-разработке в целом: https://t.me/js_web_development
