Merhabalar, şu aralar leetcode, hackerrank gibi sitelerdeki challengeları çözmeye adadım kendimi. Daha sonrasında, bunu neden forumda bir chain haline getirmeyeyim ki diye. Öncelikli olarak not düşeyim; Problemlerde aksi iddia edilmediği sürece time complexity üzerine odaklı çözüm yapmaya çalışacağım.
Gelelim problemimize. Çözmeye çalıştığım problem diyor ki: "Elimizde bir array olduğunu varsayalım. İçerisinde random rakamlar bulunmakta. Bu array ile birlikte size bir de hedef rakam vereceğiz. Amacınız, arraydaki elemanları kullanarak toplamları verilen hedef sonuca ulaşan 2 değeri return etmek. Kısıtılama olarak, her rakam sadece bir kez kullanılacaktır ve sadece 2 indis return edeceksiniz diye iki ibare mevcut. İndisden kasıt ise, rakamın array içerisinde bulunduğu yer. Soru ne kadar kolay görünse de en sondaki ulaştığım sonuca kadar toplam 37 dakika 44 saniye harcamışım.
Çözüm
Çözüm için ilk yaklaşımım tabii ki de brute force oldu. Yani ilk önce çalışan bir algoritma oluşturmam gerekliydi. Dil olarak C++ kullandım, bilginize.
Not: Tavsiyem, önce kendiniz uğraşın birazcık. Daha sonrasında buradan çözüme bakarsınız.
İlk aklıma gelen çözüm yöntemleri tabii ki başarısızlık ile sonuçlandı. Akabinde ise aklıma gelen ve ilk çalışan algoritmam şu şekildeydi:
Kod:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
for(int i = 0; i < nums.size(); i++){
for(int j = i+1; j < nums.size(); j++){
if(nums[j] == target - nums[i]){
res.push_back(i);
res.push_back(j);
return res;
}
}
}
return nums;
}
Şimdi gelelim çözümün geri kalan optimizasyon kısmınaa. Evet elimizde bir çözüm var, lakin pek de optimal değil yukarıdaki resimde gördüğünüz gibi. Şimdi burada ki asıl trick ise, böyle bir algoritmayı nasıl optimize edebiliriz sorusu. Şöyle biraz düşündükten sonra aklıma hashmap geldi. Tabii ki veri yapılarına ne kadar aşina iseniz o kadar kardasınız burada. Şuraya şöyle de küçük bir bilgi düşeyim.
Kod:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int, int> m;
vector<int> res;
for(int i = 0; i < nums.size(); i++){
int result = target - nums[i];
if(m.count(result)) {
res.push_back(m[result]);
res.push_back(i);
return res;
}
m.insert (std::pair<int, int>(nums[i], i));
}
return nums;
}
Yeni çözümümüz ise O(1) de çalışmakta yani performans bazında çok yüksek bir artış söz konusu. Lakin bu artış tabii ki bedavaya gelmiş bir şey değil, memoryde kullandığımız alan da bir artış söz konusu. Buradaki olay ise, elimizdeki hashmap'i doldururken her seferinde toplamı bize verecek olan rakamın hashmap girdisi olup olmadığını kontrol etmek. Ve yukarıdaki diagramında gösterdiği gibi, unordered_list üzerinde yaptığımız arama işlemleri constant, yani sabit zaman almakta.
Performans ölçütü olarak, şu resmi gösterebilirim. Elimizdeki arraylerin içerisinde maximum 10-15 eleman olduğunu varsayarak düşünebilirsiniz. Bu eleman sayısının milyonlarca olduğunu hayal ettiğinizde aradaki farkı hayal bile etmek istemezsiniz diye düşünüyorum.
Umarım bir şekilde faydalı olmuştur, forumda bu tarz paylaşımları arttırmayı hedefliyorum. Bir sonraki problem ve çözümüyle görüşmek dileğiyle
