Адзіны нумар


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка
масіў

Дадзены масіў a [] памерам n. Усе элементы ў масіў прысутнічаюць двойчы, за выключэннем 1. Знайдзіце элемент, які з'яўляецца толькі адзін раз, ці іншымі словамі, мы гаворым, што знайшлі адзіны лік.

Адзіны нумар

Прыклад

Уваход: a [] = {1, 3, 5, 5, 2, 1, 3}

выхад: 2

Уваход: a [] = {1, 3, 5, 5, 1}

выхад: 3

Просты метад

Праверце кожны элемент з кожным іншым элементам. Вярнуць адзінкавы элемент.

Алгарытм

  1. Ініцыялізаваць масіў a [] памерам n.
  2. Стварыце цэлалікавую зменную, каб захаваць адзін элемент у масіве і ініцыялізаваць зменную сцяга як 0
  3. Прайдзіце па масіве і абнавіце зменную сцяга як 0 і зменную для аднаго элемента як значэнне, якое захоўваецца ў бягучым індэксе ў масіве a [].
  4. Стварыце ўнутраны цыкл ад 0 да n-1 і праверце, ці значэнне, якое захоўваецца пры бягучым індэксе ў масіве a [], роўна зменнай для аднаго элемента, а бягучы індэкс унутранага цыкла не роўны бягучаму індэксу знешні цыкл, абнавіце зменную сцяга як 1.
  5. Калі зменная сцяга роўная 0, вярніце зменную для аднаго элемента.

Праграма C ++ для пошуку аднаго нумара

#include <bits/stdc++.h>
using namespace std;

int singleElement(int a[], int n){
    int single,flag=0;
    for(int i=0; i<n; i++){
        flag = 0;
        single = a[i];
        for(int j=0; j<n; j++){
            if((a[j]==single)&&(j!=i)){
                flag=1;
            }    
        }
        if(flag==0)
            return single;
    }
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

Праграма Java для пошуку аднаго нумара

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single=0,flag=0;
        for(int i=0; i<n; i++){
            flag = 0;
            single = a[i];
            for(int j=0; j<n; j++){
                if((a[j]==single)&&(j!=i)){
                    flag=1;
                }    
            }
            if(flag==0){
                return single;
            }    
        }
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

Аналіз складанасці

Складанасць часу: О (н2) дзе n - колькасць элементаў у дадзеным масіве a [].

Дапаможная прастора: O (1), таму што мы выкарыстоўвалі пастаянную дадатковую прастору.

Выкарыстанне Xor

Выкарыстанне ўласцівасцей xor -

a xor a = 0

0 xor a = a

Алгарытм

  1. Ініцыялізаваць масіў a [] памерам n.
  2. Стварыце функцыю для пошуку адзінкавага элемента ў дадзеным масіве [], які прымае цэлы масіў і памер цэлага масіва як яго параметр.
  3. Ініцыялізуйце зменную single і захавайце ў ёй першы элемент дадзенага масіва.
  4. Прайдзіце па масіве ад 1 да n-1 і абнавіце зменную single як xor самой зменнай single і значэнне ў бягучым індэксе ў дадзеным масіве.
  5. Вяртае зменную single.

Праграма C ++ для пошуку аднаго нумара

#include <bits/stdc++.h>
using namespace std;

int singleElement(int a[], int n){
    int single = a[0]; 
    for(int i=1; i<n; i++) 
        single = single ^ a[i]; 
  
    return single;
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

Праграма Java для пошуку аднаго нумара

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single = a[0]; 
        for(int i=1; i<n; i++) 
            single = single ^ a[i]; 
      
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

Аналіз складанасці

Складанасць часу: O (n), дзе n - колькасць элементаў у дадзеным масіве a [].

Дапаможная прастора: O (1), таму што мы выкарыстоўвалі пастаянную дадатковую прастору.

Спасылкі