LeetCode Sıralama - Ordering

Giriş

Not : Sıralama ve Top K Elements benzeyen problemler

Burada sıralama ile ilgili bazı sorular var. 

Sıralama problemleri genelde

1. liste/diziyi sıralayarak

2. PriorityQueue, TreeMap veya benzeri sıralı bir veri yapısı kullanarak çözülür

Sıralama Kriteri

- Multifield olabilir. 

- Kısmi olabilir. Yani dizinin sadece x özelliğine sahip elemanlarını kendi içinde sırala gibi

Örnek - Bileşik Sıralama - Multifield Ordering

Elimizde virgül ile ayrılmış kelimeler içeren bir string olsun. Bu string'i kelimelere ayırıp, en uzun olanları alfabetik sıralayıp, tekrar virgül ile birleştirmek istiyoruz.

Örneğin string "python,java,javascript" olsun. Çıktı olarak "javascript" alırız

Örneğin string "python,java,kotlin" olsun. Çıktı olarak "kotlin,python" alırız

String text = "python,java,kotlin";
String[] words = text.split(",");
Arrays.sort(word,Comparator.comparing(String::length).reversed().
                            thenComparing(String::compareTo));
int maxLength = words[0].length();
String result = Arrays.stream(words)
  .filter( s -> s.length() == maxLength)
  .collect(Collectors.joinin(","));

Örnek - Sadece tek sayıları sıralama

Bir diziyi sıralamak istiyoruz ancak  çift sayıların konumu değişmesin istiyoruz. Şöyle yaparız.

Önce hepsini sıralayıp tek sayı olanları yeni bir listeye doldururuz. Bu liste 1,3,5,7,9 olur. Daha sonra ilk liste üzerinde dolaşırız. Eğer sayı tek ise hazırlamış olduğumuz sıralı listedeki belirtilen indeksteki sayıyı alırız. Sayı çift ise zaten kendisidir.

int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};

LinkedList<Integer> stack = Arrays.stream(nonSorted)
            .sorted().filter(s -> s % 2 != 0).boxed()
            .collect(Collectors.toCollection(LinkedList::new));

int[] expected = IntStream.rangeClosed(0, nonSorted.length - 1)
       .map(s -> nonSorted[s] % 2 != 0 ? stack.pop():nonSorted[s]) 
       .toArray();

Çıktı olarak şunu alırız

int[] expected = new int[]{1, 4, 3, 2, 5, 6, 7, 8, 9, 0};

Örnek

LeetCode 665: Non-decreasing Array. Çözüm şöyle. Eğer sırayı bozan elemana mavi, bir önceki elemana yeşil, iki önceki elemana da siyah diyelim. 

Normalde sadece  mavi = yeşil yapmak yeterli. Yani mavi yukarı çıkarılır. Elimizde 3(s),4(y),2(m),5 dizisi varsa 3,4(y),4(y),5 olur. Burada siyah maviden büyük

Ancak eğer siyah maviden küçükse, yeşil = mavi yapılır. 

Çünkü elimizde 3,7(y),2(m),5 varsa mavi = yeşil yaparsak 3,7,7,5 elde ederiz. Bu da kuralı yine bozar. Ama aslında maviden sonra gelen değeri de bilmiyoruz. Eğer yeşil = mavi yaparsak 3,2,2,5 elde ederiz.

Kodu şöyle

public boolean checkPossibility(int[] nums) {
  int changes = 0;  //the number of changes
  for(int i = 1; i < nums.length && cnt<=1 ; i++){
    if(nums[i-1] > nums[i]){
      changes ++;
      if(i-2<0 || nums[i-2] <= nums[i]) 
        //siyahtan büyük iki değer var yeşil = mavi
        nums[i-1] = nums[i]; 
      else {
       //siyahtan büyük bir değer var mavi = yeşil
        nums[i] = nums[i-1];
      }
    }
  }
  return changes 
}