Дан массив, в котором каждый элемент встречается три раза, кроме одного, который встречается только один раз. Найдите элемент, который встречается один раз. Ожидаемая сложность по времени составляет O (n) и O (1) дополнительного пространства.
Примеры :
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2
In the given array all element appear three times except 2 which appears once.
Input: arr[] = {10, 20, 10, 30, 10, 30, 30}
Output: 20
In the given array all element appear three times except 20 which appears once.
Мы можем использовать сортировку, чтобы сделать это за O (nLogn) время. Мы также можем использовать хеширование, оно имеет наихудшую временную сложность O (n), но требует дополнительного пространства.
Идея состоит в том, чтобы использовать побитовые операторы для решения, которое составляет O (n) времени и использует O (1) дополнительное пространство. Решение не так просто, как другие решения на основе XOR, потому что все элементы появляются здесь нечетное количество раз. Идея взята отсюда .
Запустите цикл для всех элементов в массиве. В конце каждой итерации поддерживайте следующие два значения.
единицы: биты, появившиеся 1-й, 4-й или 7-й раз … и т. д.
twos: биты, появившиеся во второй, пятый или восьмой раз и т. д.
Наконец, мы возвращаем значение «единицы»
Как сохранить значения единиц и двойок?
«none» и «twos» инициализируются как 0. Для каждого нового элемента в массиве найдите общие биты набора в новом элементе и предыдущее значение «ones». Эти общие биты на самом деле являются битами, которые должны быть добавлены к 'двойкам'. Так что делайте побитовое ИЛИ из общего набора битов с 'двойками'. 'twos' также получает некоторые дополнительные биты, которые появляются в третий раз. Эти дополнительные биты будут удалены позже.
Обновите «единицы», выполнив XOR для нового элемента с предыдущим значением «единицы». Там могут быть некоторые биты, которые появляются в 3-й раз. Эти дополнительные биты также удаляются позже.
Обе единицы и двойки содержат те дополнительные биты, которые появляются в 3-й раз. Удалите эти дополнительные биты, обнаружив общие биты в «единиц» и «двойки».
Ниже приведена реализация вышеуказанного подхода:
C ++
#include <bits/stdc++.h>
using namespace std;
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0 ;
int common_bit_mask;
for( int i=0; i< n; i++ )
{
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
int main()
{
int arr[] = {3, 3, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element with single occurrence is "<<getSingle(arr, n);
return 0;
}
|
С
#include <stdio.h>
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0 ;
int common_bit_mask;
for( int i=0; i< n; i++ )
{
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
int main()
{
int arr[] = {3, 3, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}
|
Джава
class GFG
{
static int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for(int i=0; i<n; i++ )
{
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
public static void main(String args[])
{
int arr[] = {3, 3, 2, 3};
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
|
python3
def getSingle(arr, n):
ones = 0
twos = 0
for i in range(n):
twos = twos | (ones & arr[i])
ones = ones ^ arr[i]
common_bit_mask = ~(ones & twos)
ones &= common_bit_mask
twos &= common_bit_mask
return ones
arr = [3, 3, 2, 3]
n = len(arr)
print("The element with single occurrence is ",
getSingle(arr, n))
|
C #
using System;
class GFG
{
static int getSingle(int []arr, int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for(int i = 0; i < n; i++ )
{
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
public static void Main()
{
int []arr = {3, 3, 2, 3};
int n = arr.Length;
Console.WriteLine("The element with single" +
"occurrence is " + getSingle(arr, n));
}
}
|
PHP
<?php
function getSingle($arr, $n)
{
$ones = 0; $twos = 0 ;
$common_bit_mask;
for($i = 0; $i < $n; $i++ )
{
$twos = $twos | ($ones & $arr[$i]);
$ones = $ones ^ $arr[$i];
$common_bit_mask = ~($ones & $twos);
$ones &= $common_bit_mask;
$twos &= $common_bit_mask;
}
return $ones;
}
$arr = array(3, 3, 2, 3);
$n = sizeof($arr);
echo "The element with single " .
"occurrence is ",
getSingle($arr, $n);
?>
|
Выход :
The element with single occurrence is 2
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Далее следует другой O (n) временной сложности и O (1) метод дополнительного пространства, предложенный aj . Мы можем суммировать биты в одинаковых позициях для всех чисел и взять по модулю 3. Биты, для которых сумма не кратна 3, являются битами числа с одним вхождением.
Рассмотрим пример массива {5, 5, 5, 8}. 101, 101, 101, 1000
Сумма первых битов% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Сумма вторых битов% 3 = (0 + 0 + 0 + 0)% 0 = 0;
Сумма третьих битов% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Сумма четвертых битов% 3 = (1)% 3 = 1;
Следовательно, число, которое появляется один раз, равно 1000
Ниже приведена реализация вышеуказанного подхода:
C ++
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
int getSingle(int arr[], int n)
{
int result = 0;
int x, sum;
for (int i = 0; i < INT_SIZE; i++)
{
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++ )
{
if (arr[j] & x)
sum++;
}
if (sum % 3)
result |= x;
}
return result;
}
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The element with single occurrence is " << getSingle(arr, n);
return 0;
}
|
С
#include <stdio.h>
#define INT_SIZE 32
int getSingle(int arr[], int n)
{
int result = 0;
int x, sum;
for (int i = 0; i < INT_SIZE; i++)
{
sum = 0;
x = (1 << i);
for (int j=0; j< n; j++ )
{
if (arr[j] & x)
sum++;
}
if (sum % 3)
result |= x;
}
return result;
}
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}
|
Джава
class GFG
{
static final int INT_SIZE = 32;
static int getSingle(int arr[], int n)
{
int result = 0;
int x, sum;
for(int i=0; i<INT_SIZE; i++)
{
sum = 0;
x = (1 << i);
for(int j=0; j<n; j++)
{
if((arr[j] & x) == 0)
sum++;
}
if ((sum % 3) == 0)
result |= x;
}
return result;
}
public static void main(String args[])
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
|
Python 3
INT_SIZE = 32
def getSingle(arr, n) :
result = 0
for i in range(0, INT_SIZE) :
sm = 0
x = (1 << i)
for j in range(0, n) :
if (arr[j] & x) :
sm = sm + 1
if (sm % 3) :
result = result | x
return result
arr = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
n = len(arr)
print("The element with single occurrence is "
,getSingle(arr, n))
|
C #
using System;
class GFG
{
static int INT_SIZE = 32;
static int getSingle(int []arr, int n)
{
int result = 0;
int x, sum;
for(int i = 0; i < INT_SIZE; i++)
{
sum = 0;
x = (1 << i);
for(int j = 0; j < n; j++)
{
if((arr[j] & x) == 0)
sum++;
}
if ((sum % 3) == 0)
result |= x;
}
return result;
}
public static void Main()
{
int []arr = {12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7};
int n = arr.Length;
Console.WriteLine("The element with single " +
"occurrence is " + getSingle(arr, n));
}
}
|
PHP
<?php
$INT_SIZE= 32;
function getSingle($arr, $n)
{
global $INT_SIZE;
$result = 0;
$x; $sum;
for ($i = 0; $i < $INT_SIZE; $i++)
{
$sum = 0;
$x = (1 << $i);
for ($j = 0; $j < $n; $j++ )
{
if ($arr[$j] & $x)
$sum++;
}
if ($sum % 3)
$result |= $x;
}
return $result;
}
$arr = array (12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7);
$n = sizeof($arr);
echo "The element with single occurrence is ",
getSingle($arr, $n);
?>
|
Выход :
The element with single occurrence is 7
Другой подход, предложенный Абхишеком Шармой 44 . Добавьте каждое число один раз и умножьте сумму на 3, мы получим трижды сумму каждого элемента массива. Сохраните это как thrice_sum. Вычтите сумму всего массива из суммы thrice_sum и разделите результат на 2. Получаемое число является требуемым числом (которое появляется в массиве один раз).
Массив []: [a, a, a, b, b, b, c, c, c, d]
Математическое уравнение = (3 * (a + b + c + d) — (a + a + a + b + b + b + c + c + c + d)) / 2
Проще говоря: (3 * (sum_of_array_without_duplicates) — (sum_of_array)) / 2
let arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Required no = ( 3*(sum_of_array_without_duplicates) - (sum_of_array) ) / 2
= ( 3*(12 + 1 + 3 + 2) - (12 + 1 + 12 + 3 + 12 + 1 + 1 + 2 + 3 + 3))/2
= ( 3* 18 - 50) / 2
= (54 - 50) / 2
= 2 (required answer)
Как мы знаем, что набор не содержит дубликата элемента,
Но std :: set обычно реализуется как красно-черное дерево двоичного поиска. Вставка в эту структуру данных имеет наихудший случай сложности O (log (n)), поскольку дерево поддерживается сбалансированным. мы будем использовать набор здесь.
Ниже приведена реализация вышеуказанного подхода:
C ++
#include <bits/stdc++.h>
using namespace std;
int singleNumber(int a[],int n)
{
unordered_set<int> s(a,a+n);
int arr_sum=accumulate(a, a+n,0);
int set_sum = accumulate(s.begin(), s.end(),0);
return (3*set_sum-arr_sum)/2;
}
int main() {
int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n=sizeof(a) / sizeof(a[0]);
cout<<"The element with single occurrence is "<<singleNumber(a,n);
}
|
Джава
import java.util.*;
class GFG
{
static int singleNumber(int a[], int n)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i : a)
{
s.add(i);
}
int arr_sum = 0;
for (int i : a)
{
arr_sum += i;
}
int set_sum = 0;
for (int i : s)
{
set_sum += i;
}
return (3 * set_sum - arr_sum) / 2;
}
public static void main(String[] args)
{
int a[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = a.length;
System.out.println("The element with single " +
"occurrence is " + singleNumber(a, n));
}
}
|
python3
def singleNumber(nums):
return (3 * sum(set(nums)) - sum(nums)) / 2
a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
print ("The element with single occurrence is ",
int(singleNumber(a)))
|
C #
using System;
using System.Collections.Generic;
class GFG
{
static int singleNumber(int []a, int n)
{
HashSet<int> s = new HashSet<int>();
foreach (int i in a)
{
s.Add(i);
}
int arr_sum = 0;
foreach (int i in a)
{
arr_sum += i;
}
int set_sum = 0;
foreach (int i in s)
{
set_sum += i;
}
return (3 * set_sum - arr_sum) / 2;
}
public static void Main(String[] args)
{
int []a = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = a.Length;
Console.WriteLine("The element with single " +
"occurrence is " + singleNumber(a, n));
}
}
|
PHP
<?php
function singleNumber($a, $n)
{
$s = array();
for ($i = 0; $i < count($a); $i++)
array_push($s, $a[$i]);
$s = array_values(array_unique($s));
$arr_sum = 0;
for ($i = 0; $i < count($a); $i++)
{
$arr_sum += $a[$i];
}
$set_sum = 0;
for ($i = 0; $i < count($s); $i++)
{
$set_sum += $s[$i];
}
return (int)(((3 * $set_sum) -
$arr_sum) / 2);
}
$a = array(12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7);
$n = count($a);
print("The element with single occurrence is " .
singleNumber($a, $n));
?>
|
Выход :
The element with single occurrence is 7
Сложность времени: O (Nlog (N))
Вспомогательное пространство: O (N)
Эта статья составлена Sumit Jain и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Найдите элемент, который появляется один раз в массиве, где каждый второй элемент появляется дважды
- Найдите единственный элемент, который появляется b раз
- Найти элемент, который появляется один раз в отсортированном массиве
- Первый элемент, который появляется четное количество раз в массиве
- Нарушения счета (перестановка, при которой элемент не появляется в исходном положении)
- Максимальная разница между двумя элементами, так что более крупный элемент появляется после меньшего числа
- Найти последний элемент после удаления каждого второго элемента в массиве из n целых чисел
- Подсчитать все элементы в массиве, который появляется по крайней мере K раз после их первого появления
- Максимальное количество раз, когда str1 отображается как неперекрывающаяся подстрока в str2
- Найдите три элемента из трех разных массивов, таких что a + b + c = sum
- Найдите единственный повторяющийся элемент от 1 до n-1
- Найти пиковый элемент
- Найти три элемента из заданных трех массивов так, чтобы их сумма была X | Набор 2
- Найти дополнительный элемент во втором массиве
- Найти первый элемент в AP, кратный данному простому
Найдите элемент, который появляется один раз
0.00 (0%) 0 votes