Bir liste 1, 4, 5,9,2 verildiğinde, toplam = 6 olduğunda iki değerin olası kombinasyonlarını bulmak için bir program yazınız.

Verilen değer a = [1,4,5,9,2]. Toplam = 6 olduğunda iki değerin kombinasyonlarını bulmalı/yazdırmalıyım.

Benim kodum aşağıdaki gibidir: (O (n ^ 2) ve verimli değil). Daha iyi çözümler -

for(int out=0;out
3
Küçük N için, 1) çözümün verimli olup olmadığı önemli değildir ve 2) O (N ^ 2) O (N) 'den daha hızlı olabilir
katma yazar Stephen C, kaynak

3 cevap

  1. Tüm sayıları bir HashSet olarak yerleştirin.
  2. Dizinin üzerine yineleyin ve her bir öğe için val , 6-val HashSet içinde olup olmadığını kontrol edin.
  3. .

Bu, ev ödevi gibi göründüğünden kod göstermiyorum (eğer öyleyse, lütfen etiketleyin).

Ayrıca, kısa diziler için O (n ^ 2) çözümünüzün kesinlikle bundan daha hızlı olacağı kesin.

10
katma
Bunun oldukça standart bir görüşme sorusu olduğunu doğrulayabilirim. Görüştüğüm zaman bu, her 5 görüşmeden biri gibi geldi. Ayrıca cevabınız en iyisi ... sadece listeyi iki kez geçiyor, bu bir O (n) çözümü.
katma yazar Nicholas, kaynak
Cevap Aix için teşekkürler. Bu ev ödevi problemi değil. SD mülakat soruları için ararken yukarıdaki soruya tökezledim. Şimdi 'röportaj' etiketini ekledim.
katma yazar srock, kaynak

İlk olarak, srock ile verilen çözüm aşağıdaki gibi olmalıdır.

int length = a.length;

for(int out = 0; out < length ; out++) {
   for(int inn = 0; inn < length; inn ++) {
      if ((inn != out) && ((a[inn] + a[out]) == 6))
      sysout("The valid combination is "+a[inn]+" "+a[out])
   }
 }

Ve tabii ki bu, uzunluk * uzunluk zamanlarını tekrarlamak için gereklidir. Aix'ten de bahsedildiği gibi, Hashset ile birlikte kullanırsak, içeriklerini hiçbir zaman uzunluğuna kadar yineleyecek ve metot, hashcode kullanarak doğrudan kova konumuna gidecektir ve karşılaştırmak için verileri getirecektir. Yani bu HashSet :: yolu büyük veri için en iyisidir.

0
katma
for(int out=0;out
0
katma