問題
Int型の配列が与えられ、ソートするために必要なスワップの数をカウントするという問題
www.hackerrank.com
解き方
O(N2)の解法
この解法はバブルソートの要領で解く。
forループを２重にしてiを0 ≦ i < arr.length, jをi+1 ≦ j < arr.lengthのようにループさせた時に、arr[i] > arr[j]の条件でカウントしてあげると解ける。
O(NlogN)の解法
この解法はマージソートの要領で解く。
２つの配列をマージさせる時に、左側の配列の値が大きければ、移動させる距離の分だけカウントさせてあげることで、スワップの回数を取得することができる。
