Geçenlerde bir soru bir yerde rastladım:

1001 dizisi olduğunu varsayalım. Tamsayılar rastgele sırayla, ama sayıların her biri 1 ile 1000 arasında (dahil). Ayrıca, her sayı sadece bir kez iki kez meydana gelen bir dizi hariç dizi görünür. Diziyi sadece bir kez her öğe erişebilirsiniz varsayalım. Tekrarlanan numarasını bulmak için bir algoritma tanımlar. Eğer algoritma yardımcı depolama kullandıysanız, bunu gerektirmeyen bir algoritma bulabilir misin?

Bilmek ilgilendiğim tek şey buikinci bölümyani,yardımcı depolama kullanmadan. Herhangi bir fikrin var mı?

Güncelleme 2:Bazı insanlar XOR sayıda yinelenen bulmak için kullanarak kesmek veya bir tuzak olduğunu düşünüyorum. Hangi resmi cevabım: "aradığım olmayan bir yinelenen numarası, aradığım bir yinelenen desen bit setleri bir dizi. Ve kesinlikle XOR bit set "ler EKLEMEK daha uygun olur". :-)

Güncelleme:Sadece zevk için önce ben yatağa gidin, burada "tek satır" alternatif çözüm gerektirir sıfır ek depolama (hatta bir döngü sayacı), dokunduğu her bir dizi öğesi yalnızca bir kez, yıkıcı olmayan ve almaz ölçekte tüm :-)

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

Derleyici aslında derleme zamanında bu ifadenin ikinci yarısı hesaplayabilecek, bu yüzden "algoritma" tam olarak 1002 işlemleri yürütmek. not

Ve eğer öğe değerleri olan dizi de derleme zamanında biliyorsanız, derleyici sabit bütün deyimi optimize eder. :-)

Özgün çözüm:Doğru cevabı bulmak için çalışıyor olsa bile bu soruları sıkı gereksinimlerini karşılamak değil. Kullandığı ek bir tamsayı tutmak için döngü sayacı, ve eriştiği her dizi elemanı üç kez - iki kez okumak ve yazmak de geçerli yineleme ve bir kez okumak için bir sonraki yineleme.

En azından ek bir değişken gerekir (veya CPU) bir kayıt) dizisi gider olarak geçerli öğenin dizini depolamak için.

Kenara rağmen, burada güvenli bir şekilde MAX_İNT kadar herhangi bir N ölçek yıkıcı bir algoritma.

for (int i = 1; i < 1001; i  )
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d\n", array[1000]);

Bu senin için neden ve nasıl çalıştığını anlamaya egzersiz, basit bir ipucu ile gideceğim :-):

a ^ a = 0
0 ^ a = a