Elimizde random bir dizi olucak kullanıcı giricek bunu daha sonra ortanca sayımızı bulacağız ve buna en yakın olan değerleri döndüreceğiz kullanıcı kaç değer döndürmek isterse ve bu O(N) karmaşıklığına sahip olmalı ve sıralama algoritmaları kullanılmamalı
comments
16 references
// Comments are closed.
random dizi uzunluğu kadar tüm değerleri tararız. Ortancaya yakın derken sağ ve soldakini birden almayı mı kastediyorsun? 6 diyleim 5 ve 7 değerleri misal. Algoritmayı da array in içine atıp yapabilirsin. Daha sonra bir temporary değer içinde tek tek alarak , sonrasında kendin sıralayabilir ve bunların indekslerini belirleyebilirsin.
İndexler ve değerler elinde olur, gerisi gelir.
Sayı değeri olarak yakın mesela dizimiz 13,35,5,9,100,1,597, olsun ortadaki sayımız 9 ve k değerimiz 3 olsun 9 a sayı değeri olarak en yakın 5,13 ve 1 var bunu döndürmeli . İndekslerden yola çıkarak yapmaya çalıştım ama O(N) karmaşıklığını karşılayamıyorum.
Eğer dediğiniz gibi yapabildiyseniz yardımcı olma şansınız var mı?
Amacın median değeri bulmak hem o(n) olsun hem de sıralama kullanılmasın. Açıkçası sıralama olmadan bana biraz zor geldi.
Matematiksel olarak bakınca bile önce sıralayıp sonra ortadakini buluyorsun.
Eğer sıralama uyarsa herhangi bir sıralama algoritmasından sonra dizinin uzunluğu / 2 diyebilirsin. O indexte olacaktır. Farklı bir yaklaşımın varsa ben de bilmek isterim. Aklıma birşey gelirse buraya yazarım.
Malesef sıralama algoritması kullanılmadan çözülmeli o yüzden zaten bi çözüm bulamıyorum. Bulduğum çözümlerde de O(N) karmaşıklığını karşılayamıyorum.
O(n) olmayan nasıl bir çözüm buldun?
İçiçe döngü kullanarak. Farklarını yeni bir dizide tuttum, oradan işlemlere devam ettim.
Sıralama algoritması kullanmam yasak dedin ama aklıma başka bir fikir geldi. Bir binary tree içine koysan (dolaylı olarak yine sıralamış oluyorsun) ve tree’den gezerek çıkarsan da olabilir. Tabi tree balanced olması gerekir.
Tam kısıtın sadece sıralama algoritmalarını kullanmamaksa tree işini görür, hatta güzel de olur.
Sonra traversal algoritmalarından pre order / post order artık hangisi uygunsa kullanabilirsin.
Kodu yazmamda yardımcı olma şansınız var mı?
Kendim en son 10 yıl önce bi balanced tree yazmaya çalışmıştım. Kodu yazmak sanıyorum senin ödevin. Ben seni yönlendireyim. Öncelikle red/black, avl tree veya b+ örneklerini bi incelemen gerekiyor. Hepsi de senin işini görür. Tree’yi kendin yazmadan hazır internetten bulduğun bir tanesini de kullanmayı deneyebilirsin.
Sonra in-order, pre-order, post-order, level-order tiplerine bakman gerekir. Hangisi sana uygunsa onu kullanabilirsin.
Bu arada bu iş basit bir sıralama algoritmasıyla daha hızlı çözülür. Bunun için tree yazmak gereksiz zorlayıcı bir çaba da olabilir. Belki şu an aklımıza gelmeyen daha kolay bir yöntem de bulabilirsin.
Karar senin.
Çok teşekkür ederim
Elindeki sayıların birbirine olan uzaklıklarını hesaplasan ve ayrı ayrı dizilerde tutsan, sonra o dizileri kendi içinde yine sıralaman gerekir. Bu şekilde ilerlersin ama sıralama kısıtın ne kadar geçerli bilemedim.
while(k<yakin){
for(j=0;j<arrli.size();j++){
if(dizi[j] ==x ){ System.out.println(“SAyi :”+x); }
if(dizi[j] == y){ System.out.println(“SAyi :”+y); }
if(min > arrli.get(j)){ int temp = arrli.get(j);
if(temp== 0)
continue;
min = temp;
}
} System.out.println(“k :”+k); STACK.push(min);
arrli.remove(Integer.valueOf(min)); min = arrli.get(0);
System.out.println(arrli);
int index = STACK.pop();
x = index + dizi[eleman/2-1];
y = Math.abs(index – dizi[eleman/2-1]);
k++;
while(k Math.abs(arrli.get(j))){ int temp = arrli.get(j);
if(temp ==0 )continue; min = temp;
}
if(min < dizi[eleman/2-1]){ x = dizi[eleman/2-1] - min ; } if(min>dizi[eleman/2-1]){ x=dizi[eleman/2-1]+min;
} } arrli.remove(Integer.valueOf(min));
// System.out.println(arrli);
// System.out.println(“min :”+min); System.out.println(“x :”+x);
k++;
}
Böyle iki tane kod yazdım ama karmaşıklıklarından emin olamadım. Bu konuda yardımcı olma şansınız var mı? Bunların karmaşıklıkları O(N) midir?
Bunlar exponantiel karmaşıklıkta n2