[]
bir algoritma sorusu
merhabalar, bahsi geçen soru şurada: www.hackerrank.com
hackerrank'ta algorithms > implementation sorularının yukarıda verdiğim soru hariç tamamını çözebildim. lakin yukarıdaki sorunun çözüm mantığını bir türlü oturtamadım. aylar boyu soruyu çözemeyince en sonunda ipuçlarıyla soruyu çözsem de hala mantığını anlamadım. anlayan biri bana anlatabilirse çok iyi olur.
çözüm şöyle: dizinin tüm elemanlarını birbirleriyle karşılaştırıyoruz. i < j olmak koşuluyla eğer a[i] > a[j] ise eğer buna ters durum diyelim. eğer toplam ters durum sayısı çift bir sayı ise çözüm TRUE, değil ise FALSE oluyor. bunun mantığı nedir?
bu da c kodu: i.hizliresim.com
hackerrank'ta algorithms > implementation sorularının yukarıda verdiğim soru hariç tamamını çözebildim. lakin yukarıdaki sorunun çözüm mantığını bir türlü oturtamadım. aylar boyu soruyu çözemeyince en sonunda ipuçlarıyla soruyu çözsem de hala mantığını anlamadım. anlayan biri bana anlatabilirse çok iyi olur.
çözüm şöyle: dizinin tüm elemanlarını birbirleriyle karşılaştırıyoruz. i < j olmak koşuluyla eğer a[i] > a[j] ise eğer buna ters durum diyelim. eğer toplam ters durum sayısı çift bir sayı ise çözüm TRUE, değil ise FALSE oluyor. bunun mantığı nedir?
bu da c kodu: i.hizliresim.com
şöyle;
i<j olmak koşuluyla a[i]>a[j]leri saymak number of inversion bulmak anlamına geliyo.
şimdi herhangi bi üçlü grubun number of inversionının burda verilen rotate fonksiyonuyla nasıl değiştiğine bakarsanız; ya hep çift ya hep tek sayı olduğunu görecekseniz. ve sorted bi arrayin number of inversionı da 0. yani number of inversion çiftse rotate ede ede sort edilebilir. eğer değilse edilemez.
i<j olmak koşuluyla a[i]>a[j]leri saymak number of inversion bulmak anlamına geliyo.
şimdi herhangi bi üçlü grubun number of inversionının burda verilen rotate fonksiyonuyla nasıl değiştiğine bakarsanız; ya hep çift ya hep tek sayı olduğunu görecekseniz. ve sorted bi arrayin number of inversionı da 0. yani number of inversion çiftse rotate ede ede sort edilebilir. eğer değilse edilemez.
- ghilleinthemist
(09.08.17 17:00:45)
1
