Menemukan duplikat dalam ruang O (n) dan O (1)

Input: Diberikan sebuah array dari n elemen yang berisi elemen dari 0 hingga n-1, dengan salah satu dari angka-angka ini muncul berapa kali.

Sasaran: Untuk menemukan bilangan berulang ini dalam O (n) dan hanya menggunakan ruang memori yang konstan.

Misalnya, misalkan n menjadi 7 dan array menjadi {1, 2, 3, 1, 3, 0, 6}, jawabannya harus 1 & 3. Saya memeriksa pertanyaan serupa di sini tetapi jawabannya menggunakan beberapa struktur data seperti HashSetdll.

Algoritma yang efisien untuk hal yang sama?

Inilah yang saya dapatkan, yang tidak memerlukan sedikit tanda tambahan:

for i := 0 to n - 1
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 0 to n - 1
    if A[i] != i then 
        print A[i]
    end if
end for

Perulangan pertama mengijinkan array sehingga jika elemen xhadir setidaknya satu kali, maka salah satu entri tersebut akan berada pada posisi A[x].

Perhatikan bahwa itu mungkin tidak terlihat O (n) pada blush pertama, tetapi ini - meskipun memiliki loop bersarang, itu masih berjalan O(N)tepat waktu. Swap hanya terjadi jika ada isehingga A[i] != i, dan masing-masing Swap set setidaknya satu elemen sehingga A[i] == i, di mana itu tidak benar sebelumnya. Ini berarti bahwa jumlah total swap (dan dengan demikian jumlah total eksekusi dari whilebadan perulangan) paling banyak N-1.

Loop kedua mencetak nilai xyang A[x]tidak sama x- karena loop pertama menjamin bahwa jika xada setidaknya satu kali dalam array, salah satu instance akan berada di A[x], ini berarti mencetak nilai-nilai xyang tidak ada di larik.

(Tautan Ideone sehingga Anda dapat bermain dengannya)

Jawaban brilian caf mencetak setiap angka yang muncul k kali dalam larik k-1 kali. Itu perilaku yang berguna, tetapi pertanyaannya bisa dibilang memanggil setiap duplikat untuk dicetak sekali saja, dan dia menyinggung kemungkinan melakukan ini tanpa meniup batas ruang waktu / konstan linier. Ini dapat dilakukan dengan mengganti loop keduanya dengan pseudocode berikut:

for (i = 0; i < N; ++i) {
    if (A[i] != i && A[A[i]] == A[i]) {
        print A[i];
        A[A[i]] = i;
    }
}

Ini mengeksploitasi properti yang setelah loop pertama dijalankan, jika ada nilai yang mmuncul lebih dari satu kali, maka salah satu kemunculan tersebut dijamin berada pada posisi yang benar, yaituA[m] . Jika kita berhati-hati kita dapat menggunakan lokasi "rumah" itu untuk menyimpan informasi tentang apakah ada duplikat yang telah dicetak atau belum.

Dalam versi caf, saat kita menelusuri array, A[i] != itersirat bahwa itu A[i]adalah duplikat. Dalam versi saya, saya mengandalkan invarian yang sedikit berbeda: yang A[i] != i && A[A[i]] == A[i]menyiratkan bahwa itu A[i]adalah duplikat yang belum pernah kita lihat sebelumnya . (Jika Anda membuang bagian "yang belum pernah kami lihat sebelumnya", sisanya dapat dilihat tersirat oleh kebenaran dari ketidak-beraturan kafe, dan jaminan bahwa semua duplikat memiliki beberapa salinan di lokasi rumah.) Properti ini berlaku di permulaan (setelah loop pertama kafe selesai) dan saya tunjukkan di bawah bahwa itu dipertahankan setelah setiap langkah.

Saat kita menelusuri larik, keberhasilan pada A[i] != ibagian pengujian menyiratkan bahwa A[i] bisa jadi duplikat yang belum pernah terlihat sebelumnya. Jika kita belum pernah melihatnya sebelumnya, maka kita berharap A[i]lokasi rumah mengarah ke dirinya sendiri - itulah yang diuji pada paruh kedua ifkondisi tersebut. Jika demikian, kami mencetaknya dan mengubah lokasi rumah agar mengarah kembali ke duplikat yang pertama ditemukan ini, membuat "siklus" 2 langkah.

Untuk melihat bahwa operasi ini tidak mengubah invarian kami, anggaplah m = A[i]untuk posisi tertentu imemuaskan A[i] != i && A[A[i]] == A[i]. Jelas bahwa perubahan yang kita buat ( A[A[i]] = i) akan berfungsi untuk mencegah kejadian non-rumah lainnya mmenjadi keluaran sebagai duplikat dengan menyebabkan paruh kedua dari ifkondisi mereka gagal, tetapi apakah itu akan berfungsi ketika itiba di lokasi rumah m,? Ya itu akan, karena sekarang, meskipun pada yang baru ini ikami menemukan bahwa paruh pertama dari ifkondisi, A[i] != ibenar, paruh ke-2 menguji apakah lokasi yang ditunjuknya adalah lokasi rumah dan ternyata bukan. Dalam situasi ini kami tidak lagi mengetahui apakah nilai duplikat matau A[m]merupakan nilai duplikat, tetapi kami tahu bahwa bagaimanapun juga,sudah dilaporkan , karena 2 siklus ini dijamin tidak akan muncul di hasil loop pertama kafe. (Perhatikan bahwa jika m != A[m]maka tepat satu dari mdan A[m]terjadi lebih dari sekali, dan yang lainnya tidak terjadi sama sekali.)

Ini pseudocode-nya

for i <- 0 to n-1:
   if (A[abs(A[i])]) >= 0 :
       (A[abs(A[i])]) = -(A[abs(A[i])])
   else
      print i
end for

Kode contoh di C ++

Untuk N yang relatif kecil kita dapat menggunakan operasi div / mod

n.times do |i|
  e = a[i]%n
  a[e] += n
end

n.times do |i| 
  count = a[i]/n
  puts i if count > 1
end

Bukan C / C ++ tapi bagaimanapun juga

http://ideone.com/GRZPI

Tidak terlalu cantik tapi setidaknya mudah untuk melihat properti O (N) dan O (1). Pada dasarnya kami memindai larik dan, untuk setiap nomor kami melihat apakah posisinya telah ditandai sudah-terlihat-sekali (N) atau sudah-terlihat-beberapa kali (N + 1). Jika itu ditandai sudah-terlihat-sekali, kami mencetaknya dan menandainya sudah-terlihat-beberapa kali. Jika tidak ditandai, kami menandainya sudah-terlihat-sekali dan kami memindahkan nilai asli dari indeks terkait ke posisi saat ini (penandaan adalah operasi yang merusak).

for (i=0; i<a.length; i++) {
  value = a[i];
  if (value >= N)
    continue;
  if (a[value] == N)  {
    a[value] = N+1; 
    print value;
  } else if (a[value] < N) {
    if (value > i)
      a[i--] = a[value];
    a[value] = N;
  }
}

atau, lebih baik lagi (lebih cepat, meskipun ada putaran ganda):

for (i=0; i<a.length; i++) {
  value = a[i];
  while (value < N) {
    if (a[value] == N)  {
      a[value] = N+1; 
      print value;
      value = N;
    } else if (a[value] < N) {
      newvalue = value > i ? a[value] : N;
      a[value] = N;
      value = newvalue;
    }
  }
}

Salah satu solusi di C adalah:

#include <stdio.h>

int finddup(int *arr,int len)
{
    int i;
    printf("Duplicate Elements ::");
    for(i = 0; i < len; i++)
    {
        if(arr[abs(arr[i])] > 0)
          arr[abs(arr[i])] = -arr[abs(arr[i])];
        else if(arr[abs(arr[i])] == 0)
        {
             arr[abs(arr[i])] = - len ;
        }
        else
          printf("%d ", abs(arr[i]));
    }

}
int main()
{   
    int arr1[]={0,1,1,2,2,0,2,0,0,5};
    finddup(arr1,sizeof(arr1)/sizeof(arr1[0]));
    return 0;
}

Ini adalah kompleksitas ruang O (n) waktu dan O (1).

Mari kita asumsikan bahwa kita menyajikan larik ini sebagai struktur data graf searah - setiap bilangan adalah simpul dan indeksnya dalam larik menunjuk ke simpul lain yang membentuk tepi graf.

Untuk lebih mudahnya kami memiliki indeks 0 hingga n-1 dan rentang angka dari 0..n-1. misalnya

   0  1  2  3  4 
 a[3, 2, 4, 3, 1]

0 (3) -> 3 (3) adalah sebuah siklus.

Jawaban: Lintasi saja larik dengan mengandalkan indeks. jika a [x] = a [y] maka itu adalah siklus dan duplikat. Lompat ke indeks berikutnya dan lanjutkan lagi dan seterusnya hingga akhir dari sebuah array. Kompleksitas: O (n) waktu dan O (1) ruang.

Kode python kecil untuk mendemonstrasikan metode caf di atas:

a = [3, 1, 1, 0, 4, 4, 6] 
n = len(a)
for i in range(0,n):
    if a[ a[i] ] != a[i]: a[a[i]], a[i] = a[i], a[a[i]]
for i in range(0,n):
    if a[i] != i: print( a[i] )

Algoritma dapat dilihat pada fungsi C berikut. Mengambil larik asli, meskipun tidak diperlukan, dapat dilakukan dengan mengambil setiap entri modulo n .

void print_repeats(unsigned a[], unsigned n)
{
    unsigned i, _2n = 2*n;
    for(i = 0; i < n; ++i) if(a[a[i] % n] < _2n) a[a[i] % n] += n;
    for(i = 0; i < n; ++i) if(a[i] >= _2n) printf("%u ", i);
    putchar('\n');
}

Ideone Link untuk pengujian.

static void findrepeat()
{
    int[] arr = new int[7] {0,2,1,0,0,4,4};

    for (int i = 0; i < arr.Length; i++)
    {
        if (i != arr[i])
        {
            if (arr[i] == arr[arr[i]])
            {
                Console.WriteLine(arr[i] + "!!!");
            }

            int t = arr[i];
            arr[i] = arr[arr[i]];
            arr[t] = t;
        }
    }

    for (int j = 0; j < arr.Length; j++)
    {
        Console.Write(arr[j] + " ");
    }
    Console.WriteLine();

    for (int j = 0; j < arr.Length; j++)
    {
        if (j == arr[j])
        {
            arr[j] = 1;
        }
        else
        {
            arr[arr[j]]++;
            arr[j] = 0;
        }
    }

    for (int j = 0; j < arr.Length; j++)
    {
        Console.Write(arr[j] + " ");
    }
    Console.WriteLine();
}

Saya telah membuat satu aplikasi contoh taman bermain dengan cepat untuk menemukan duplikat dalam 0 (n) kompleksitas waktu dan ruang ekstra yang konstan. Silakan periksa url Finding Duplicates

Solusi IMP Di atas bekerja ketika sebuah array berisi elemen dari 0 hingga n-1, dengan salah satu dari angka-angka ini muncul beberapa kali.

private static void printRepeating(int arr[], int size) {
        int i = 0;
        int j = 1;
        while (i < (size - 1)) {
            if (arr[i] == arr[j]) {
                System.out.println(arr[i] + " repeated at index " + j);
                j = size;
            }
            j++;
            if (j >= (size - 1)) {
                i++;
                j = i + 1;
            }
        }

    }

Jika array tidak terlalu besar, solusi ini lebih sederhana, Ini membuat array lain dengan ukuran yang sama untuk ticking.

1 Buat bitmap / larik dengan ukuran yang sama dengan larik masukan Anda

 int check_list[SIZE_OF_INPUT];
 for(n elements in checklist)
     check_list[i]=0;    //initialize to zero

2 pindai larik masukan Anda dan tingkatkan jumlahnya dalam larik di atas

for(i=0;i<n;i++) // every element in input array
{
  check_list[a[i]]++; //increment its count  
}  

3 Sekarang pindai array check_list dan cetak duplikatnya sekali atau sebanyak yang telah diduplikasi

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

    if(check_list[i]>1) // appeared as duplicate
    {
        printf(" ",i);  
    }
}

Tentu saja dibutuhkan dua kali ruang yang dikonsumsi oleh solusi yang diberikan di atas, tetapi efisiensi waktu adalah O (2n) yang pada dasarnya O (n).