Temukan Integer Terkecil Tidak dalam Daftar

Pertanyaan wawancara menarik yang digunakan kolega saya:

Misalkan Anda diberikan daftar bilangan bulat 64-bit tak bertanda tangan yang sangat panjang dan tidak disortir. Bagaimana Anda menemukan bilangan bulat non-negatif terkecil yang tidak muncul dalam daftar?

TINDAK LANJUT: Sekarang solusi yang jelas dengan menyortir telah diusulkan, dapatkah Anda melakukannya lebih cepat daripada O (n log n)?

TINDAK LANJUT: Algoritme Anda harus berjalan di komputer dengan, katakanlah, memori 1GB

KLARIFIKASI: Daftar ini ada di RAM, meskipun mungkin menghabiskan banyak. Anda diberi ukuran daftarnya, katakanlah N, di muka.

Jika struktur data dapat dimutasi pada tempatnya dan mendukung akses acak maka Anda dapat melakukannya dalam waktu O (N) dan O (1) ruang tambahan. Hanya melalui array secara berurutan dan untuk setiap indeks tulis nilai pada indeks ke indeks yang ditentukan oleh nilai, secara rekursif menempatkan nilai apa pun di lokasi itu ke tempatnya dan membuang nilai> N. Kemudian pergi lagi melalui array untuk mencari tempat di mana nilai tidak cocok dengan indeks - itu adalah nilai terkecil yang tidak ada dalam larik. Ini menghasilkan paling banyak perbandingan 3N dan hanya menggunakan beberapa nilai ruang sementara.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

Berikut O(N)solusi sederhana yang menggunakan O(N)ruang. Saya berasumsi bahwa kami membatasi daftar input ke bilangan non-negatif dan kami ingin mencari bilangan non-negatif pertama yang tidak ada dalam daftar.

1. Temukan panjang daftar; katakanlah itu N.
2. Alokasikan array Nboolean, diinisialisasi ke semua false.
3. Untuk setiap angka Xdalam daftar, jika Xkurang dari N, setel X'thelemen larik ke true.
4. Scan array mulai dari index 0, cari elemen pertama yaitu false. Jika Anda menemukan yang pertama falsedi indeks I, maka Iitulah jawabannya. Sebaliknya (yaitu ketika semua elemen true) jawabannya adalah N.

Dalam praktiknya, "array Nboolean" mungkin akan dikodekan sebagai "bitmap" atau "bitset" yang direpresentasikan sebagai array byteatau int. Ini biasanya menggunakan lebih sedikit ruang (tergantung pada bahasa pemrograman) dan memungkinkan pemindaian untuk yang pertama falsedilakukan lebih cepat.

Inilah bagaimana / mengapa algoritma bekerja.

Misalkan Nangka dalam daftar tidak berbeda, atau salah satu atau lebih dari angka tersebut lebih besar dari N. Artinya, setidaknya harus ada satu angka dalam rentang 0 .. N - 1yang tidak ada dalam daftar. Jadi masalah mencari bilangan hilang terkecil karenanya harus dikurangi menjadi masalah menemukan bilangan hilang terkecil kurang dariN . Ini berarti kita tidak perlu melacak angka yang lebih besar atau sama denganN ... karena itu bukan jawabannya.

Alternatif dari paragraf sebelumnya adalah bahwa list tersebut merupakan permutasi dari bilangan-bilangan tersebut 0 .. N - 1. Dalam kasus ini, langkah 3 menetapkan semua elemen array ke true, dan langkah 4 memberi tahu kita bahwa nomor "hilang" pertama adalah N.

Kompleksitas komputasi algoritma ini O(N)dengan konstanta proporsionalitas yang relatif kecil. Itu membuat dua linier melewati daftar, atau hanya satu lulus jika panjang daftar diketahui untuk memulai. Tidak perlu mewakili seluruh daftar dalam memori, jadi penggunaan memori asimtotik algoritme adalah apa yang diperlukan untuk mewakili array boolean; yaitu O(N)bit.

(Sebaliknya, algoritme yang mengandalkan penyortiran atau partisi dalam memori mengasumsikan bahwa Anda dapat mewakili seluruh daftar dalam memori. Dalam bentuk pertanyaan yang diajukan, ini akan membutuhkan O(N)kata 64-bit.)

Komentar @Jorn bahwa langkah 1 hingga 3 adalah variasi dalam urutan penghitungan. Dalam arti tertentu dia benar, tetapi perbedaannya signifikan:

• Pengurutan penghitungan memerlukan larik (setidaknya) Xmax - Xminpenghitung Xmaxdengan angka terbesar dalam daftar dan Xminmerupakan angka terkecil dalam daftar. Setiap penghitung harus dapat mewakili N status; yaitu mengasumsikan representasi biner itu harus memiliki tipe integer (setidaknya) ceiling(log2(N))bit.
• Untuk menentukan ukuran larik, pengurutan penghitungan perlu melewati awal daftar untuk menentukan Xmaxdan Xmin.
• Oleh karena itu, persyaratan ruang kasus terburuk minimum adalah ceiling(log2(N)) * (Xmax - Xmin)bit.

Sebaliknya, algoritme yang disajikan di atas hanya membutuhkan Nbit dalam kasus terburuk dan terbaik.

Namun, analisis ini mengarah pada intuisi bahwa jika algoritme membuat awal melewati daftar mencari nol (dan menghitung elemen daftar jika diperlukan), itu akan memberikan jawaban yang lebih cepat tanpa menggunakan spasi sama sekali jika menemukan nol. Ini pasti layak dilakukan jika ada kemungkinan besar untuk menemukan setidaknya satu nol dalam daftar. Dan operan ekstra ini tidak mengubah keseluruhan kompleksitas.

EDIT: Saya telah mengubah deskripsi algoritme untuk menggunakan "array boolean" karena orang-orang tampaknya menganggap deskripsi asli saya menggunakan bit dan bitmap membingungkan.

Karena OP sekarang telah menentukan bahwa daftar asli disimpan dalam RAM dan bahwa komputer hanya memiliki, katakanlah, 1GB memori, saya akan mengambil risiko dan memprediksi bahwa jawabannya adalah nol.

RAM 1GB berarti daftar tersebut dapat memiliki paling banyak 134.217.728 nomor di dalamnya. Tetapi ada 2 ⁶⁴ = 18.446.744.073.709.551.616 kemungkinan nomor. Jadi probabilitas bahwa nol ada dalam daftar adalah 1 dari 137.438.953.472.

Sebaliknya, peluang saya disambar petir tahun ini adalah 1 berbanding 700.000. Dan peluang saya terkena meteorit adalah sekitar 1 banding 10 triliun. Jadi saya sekitar sepuluh kali lebih mungkin untuk ditulis dalam jurnal ilmiah karena kematian saya yang terlalu dini oleh benda langit daripada jawabannya bukan nol.

Seperti yang ditunjukkan dalam jawaban lain, Anda dapat melakukan penyortiran, lalu memindai hingga Anda menemukan celah.

Anda dapat meningkatkan kompleksitas algoritmik menjadi O (N) dan mempertahankan ruang O (N) dengan menggunakan QuickSort yang dimodifikasi di mana Anda menghilangkan partisi yang bukan kandidat potensial untuk memuat celah.

• Pada fase partisi pertama, hapus duplikat.
• Setelah partisi selesai, lihat jumlah item di partisi bawah
• Apakah nilai ini sama dengan nilai yang digunakan untuk membuat partisi?
  • Jika demikian maka itu berarti bahwa celah tersebut berada di partisi yang lebih tinggi.
    • Lanjutkan dengan quicksort, abaikan partisi bawah
  • Jika tidak, celahnya ada di partisi bawah
    • Lanjutkan dengan quicksort, abaikan partisi yang lebih tinggi

Ini menghemat banyak perhitungan.

Untuk mengilustrasikan salah satu perangkap O(N)pemikiran, berikut adalah O(N)algoritma yang menggunakan O(1)ruang.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Karena angkanya semuanya 64 bit, kita bisa menggunakan radix sort padanya, yaitu O (n). Sortir, lalu pindai hingga Anda menemukan yang Anda cari.

jika angka terkecil adalah nol, pindai ke depan hingga Anda menemukan celah. Jika bilangan terkecil bukan nol, jawabannya nol.

Untuk metode hemat ruang dan semua nilai berbeda, Anda dapat melakukannya dalam ruang O( k )dan waktu O( k*log(N)*N ). Ini hemat ruang dan tidak ada pemindahan data dan semua operasi adalah dasar (menambahkan pengurangan).

1. set U = N; L=0
2. Pertama partisi ruang nomor di kdaerah. Seperti ini:
   • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L...0->(U-L) + L
3. Temukan berapa banyak angka ( count{i}) di setiap wilayah. (N*k langkah)
4. Temukan region pertama ( h) yang tidak penuh. Artinya count{h} < upper_limit{h}. (k langkah)
5. jika h - count{h-1} = 1 Anda sudah mendapatkan jawabannya
6. set U = count{h}; L = count{h-1}
7. kebagian 2

ini dapat ditingkatkan menggunakan hashing (terima kasih untuk Nic ide ini).

1. sama
2. Pertama partisi ruang nomor di kdaerah. Seperti ini:
   • L + (i/k)->L + (i+1/k)*(U-L)
3. inc count{j} menggunakan j = (number - L)/k (if L < number < U)
4. temukan wilayah pertama (h ) yang tidak memiliki elemen k di dalamnya
5. jika count{h} = 1 h adalah jawaban Anda
6. set U = maximum value in region h L = minimum value in region h

Ini akan masuk O(log(N)*N).

Saya hanya akan mengurutkannya kemudian menjalankan urutannya sampai saya menemukan celah (termasuk celah di awal antara nol dan angka pertama).

Dalam hal algoritme, sesuatu seperti ini akan melakukannya:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Tentu saja, jika Anda memiliki lebih banyak memori daripada CPU grunt, Anda dapat membuat bitmask dari semua kemungkinan nilai 64-bit dan cukup mengatur bit untuk setiap angka dalam daftar. Kemudian cari 0-bit pertama di bitmask itu. Itu mengubahnya menjadi operasi O (n) dalam hal waktu tetapi sangat mahal dalam hal persyaratan memori :-)

Saya ragu Anda dapat meningkatkan O (n) karena saya tidak dapat melihat cara melakukannya yang tidak melibatkan melihat setiap angka setidaknya sekali.

Algoritme untuk yang satu itu akan berada di sepanjang baris:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

Sortir daftarnya, lihat elemen pertama dan kedua, dan mulai naik hingga ada celah.

Anda dapat melakukannya dalam O (n) waktu dan O (1) ruang tambahan, meskipun faktor tersembunyinya cukup besar. Ini bukanlah cara praktis untuk menyelesaikan masalah, tetapi mungkin tetap menarik.

Untuk setiap integer 64-bit unsigned (dalam urutan menaik) iterasi daftar sampai Anda menemukan integer target atau Anda mencapai akhir daftar. Jika Anda mencapai akhir daftar, bilangan bulat target adalah bilangan bulat terkecil yang tidak ada dalam daftar. Jika Anda mencapai akhir dari bilangan bulat 64-bit, setiap bilangan bulat 64-bit ada dalam daftar.

Ini dia sebagai fungsi Python:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Fungsi ini sengaja tidak efisien agar tetap O (n). Perhatikan terutama bahwa fungsi tersebut terus memeriksa bilangan bulat target bahkan setelah jawabannya ditemukan. Jika fungsi dikembalikan segera setelah jawabannya ditemukan, berapa kali loop luar berlari akan dibatasi oleh ukuran jawaban, yang dibatasi oleh n. Perubahan itu akan membuat run time menjadi O (n ^ 2), meskipun akan jauh lebih cepat.

Terima kasih kepada egon, swilden, dan Stephen C untuk inspirasi saya. Pertama, kami mengetahui batasan nilai sasaran karena tidak boleh lebih besar dari ukuran daftar. Selain itu, daftar 1 GB dapat berisi paling banyak 134217728 (128 * 2 ^ 20) bilangan bulat 64-bit.

Bagian
hashing yang saya usulkan menggunakan hashing untuk secara dramatis mengurangi ruang pencarian kami. Pertama, akar kuadrat ukuran list. Untuk daftar 1GB, itu N = 11.586. Siapkan array bilangan bulat berukuran N. Iterasi melalui daftar, dan ambil akar kuadrat * dari setiap angka yang Anda temukan sebagai hash. Di tabel hash Anda, tambahkan penghitung untuk hash itu. Selanjutnya, lakukan iterasi melalui tabel hash Anda. Keranjang pertama yang Anda temukan yang tidak sama dengan ukuran maksimalnya menentukan ruang pencarian baru Anda.

Bagian Bitmap
Sekarang atur peta bit biasa yang sama dengan ukuran ruang pencarian baru Anda, dan ulangi lagi melalui daftar sumber, isi bitmap saat Anda menemukan setiap nomor di ruang pencarian Anda. Setelah selesai, bit pertama yang tidak disetel di bitmap Anda akan memberikan jawaban.

Ini akan diselesaikan dalam ruang O (n) waktu dan O (sqrt (n)).

(* Anda dapat menggunakan sesuatu seperti bit shifting untuk melakukan ini dengan lebih efisien, dan cukup variasikan jumlah dan ukuran bucket yang sesuai.)

Nah, jika hanya ada satu angka yang hilang dalam daftar angka, cara termudah untuk menemukan angka yang hilang adalah dengan menjumlahkan deretan dan mengurangkan setiap nilai dalam daftar. Nilai akhir adalah angka yang hilang.

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Kita bisa menggunakan tabel hash untuk menampung angka. Setelah semua angka selesai, jalankan penghitung dari 0 hingga kami menemukan yang terendah. Hash yang cukup baik akan di-hash dan disimpan dalam waktu yang konstan, dan diambil dalam waktu yang konstan.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Kasus terburuk jika ada nelemen dalam larik, dan {0, 1, ... n-1}, dalam hal ini, jawabannya akan diperoleh di n, tetap menyimpannya O(n).

Inilah jawaban saya yang tertulis di Jawa:

Ide Dasar: 1- Loop melalui array membuang duplikat bilangan positif, nol, dan negatif sambil menjumlahkan sisanya, mendapatkan bilangan positif maksimum juga, dan menyimpan bilangan positif unik dalam Peta.

2- Hitung jumlahnya sebagai max * (max + 1) / 2.

3- Temukan perbedaan antara jumlah yang dihitung pada langkah 1 & 2

4- Ulangi lagi dari 1 ke minimum [jumlah selisih, maks] dan kembalikan nomor pertama yang tidak ada di peta yang diisi pada langkah 1.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Seperti yang ditunjukkan oleh Stephen C dengan cerdik, jawabannya harus berupa angka yang lebih kecil dari panjang array. Saya kemudian akan menemukan jawabannya dengan pencarian biner. Ini mengoptimalkan kasus terburuk (sehingga pewawancara tidak dapat menangkap Anda dalam skenario patologis 'bagaimana jika'). Dalam sebuah wawancara, tunjukkan bahwa Anda melakukan ini untuk mengoptimalkan kasus terburuk.

Cara menggunakan penelusuran biner adalah mengurangi angka yang Anda cari dari setiap elemen larik, dan memeriksa hasil negatif.

Saya suka pendekatan "tebak nol". Jika angkanya acak, kemungkinan besar nol. Jika "pemeriksa" menyetel daftar non-acak, tambahkan satu dan tebak lagi:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

Kasus terburuknya adalah n * N dengan n = N, tetapi dalam praktiknya n sangat mungkin menjadi bilangan kecil (mis. 1)

Saya tidak yakin apakah saya mendapat pertanyaan itu. Namun jika untuk list 1,2,3,5,6 dan angka yang hilang adalah 4, maka angka yang hilang tersebut dapat ditemukan di O (n) dengan cara: (n + 2) (n + 1) / 2- (n + 1) tidak ada / 2

EDIT: maaf, saya kira saya berpikir terlalu cepat tadi malam. Bagaimanapun, bagian kedua sebenarnya harus diganti dengan sum (daftar), di mana O (n) berasal. Rumusnya mengungkapkan ide di baliknya: untuk n bilangan bulat berurutan, jumlahnya harus (n + 1) * n / 2. Jika ada nomor yang hilang, jumlahnya akan sama dengan jumlah (n + 1) bilangan bulat berurutan dikurangi nomor yang hilang.

Terima kasih telah menunjukkan fakta bahwa saya meletakkan beberapa bagian tengah dalam pikiran saya.

Bagus Semut Aasma! Saya memikirkan jawabannya selama sekitar 15 menit dan secara independen muncul dengan jawaban yang serupa dengan pemikiran Anda:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m mewakili "kemungkinan keluaran maksimum saat ini mengingat apa yang saya ketahui tentang masukan i pertama dan dengan asumsi tidak ada yang lain tentang nilai-nilai sampai entri di m-1".

Nilai m ini akan dikembalikan hanya jika (a [i], ..., a [m-1]) adalah permutasi dari nilai (i, ..., m-1). Jadi jika a [i]> = m atau jika a [i] <i atau jika a [i] == a [a [i]] kita tahu bahwa m adalah keluaran yang salah dan harus setidaknya satu elemen lebih rendah. Jadi mengurangi m dan menukar a [i] dengan a [m] kita bisa mengulang.

Jika ini tidak benar tetapi a [i]> i maka mengetahui bahwa a [i]! = A [a [i]] kita tahu bahwa menukar [i] dengan [a [i]] akan meningkatkan jumlah elemen di tempat mereka sendiri.

Jika tidak, a [i] harus sama dengan i dalam hal ini kita dapat menaikkan i dengan mengetahui bahwa semua nilai hingga dan termasuk indeks ini sama dengan indeksnya.

Bukti bahwa ini tidak bisa memasuki putaran tak terbatas ditinggalkan sebagai latihan bagi pembaca. :)

The Dafny fragmen dari Semut jawabannya menunjukkan mengapa algoritma di-tempat mungkin gagal. The requirespra-kondisi menjelaskan bahwa nilai-nilai masing-masing item tidak harus melampaui batas-batas array.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn't match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Tempel kode ke validator dengan dan tanpa forall ...klausa untuk melihat kesalahan verifikasi. Kesalahan kedua adalah akibat dari pemverifikasi tidak dapat menetapkan kondisi penghentian untuk loop Lulus 1. Membuktikan ini diserahkan kepada seseorang yang lebih memahami alat tersebut.

Berikut adalah jawaban di Java yang tidak mengubah input dan menggunakan waktu O (N) dan N bit ditambah sedikit overhead memori konstan (di mana N adalah ukuran daftar):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = ['X' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == 'X':
        return count
    count +=1
return target[count-1] + 1

Dapatkan 100% untuk solusi di atas.

1) Filter negatif dan Nol

2) Sortir / berbeda

3) Kunjungi array

Kompleksitas : O (N) atau O (N * log (N))

menggunakan Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Sebuah unordered_set dapat digunakan untuk menyimpan semua bilangan positif, dan kemudian kita dapat beralih dari 1 ke panjang unordered_set, dan melihat bilangan pertama yang tidak muncul.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of 'i'

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Solusi melalui javascript dasar

var a = [1, 3, 6, 4, 1, 2];

function findSmallest(a) {
var m = 0;
  for(i=1;i<=a.length;i++) {
    j=0;m=1;
    while(j < a.length) {
      if(i === a[j]) {
        m++;
      }
      j++;
    }
    if(m === 1) {
      return i;
    }
  }
}

console.log(findSmallest(a))

Semoga ini bisa membantu seseorang.

Dengan python itu bukan yang paling efisien, tapi benar

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime

# write your code in Python 3.6

def solution(A):
    MIN = 0
    MAX = 1000000
    possible_results = range(MIN, MAX)

    for i in possible_results:
        next_value = (i + 1)
        if next_value not in A:
            return next_value
    return 1

test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))

def solution(A):
    A.sort()
    j = 1
    for i, elem in enumerate(A):
        if j < elem:
            break
        elif j == elem:
            j += 1
            continue
        else:
            continue
    return j

ini dapat membantu:

0- A is [5, 3, 2, 7];
1- Define B With Length = A.Length;                            (O(1))
2- initialize B Cells With 1;                                  (O(n))
3- For Each Item In A:
        if (B.Length <= item) then B[Item] = -1                (O(n))
4- The answer is smallest index in B such that B[index] != -1  (O(n))