You are viewing a single comment's thread. Return to all comments →
I found another way to achieve the objective, this problem is very close to the minimum swaps problem, wich the objective is count the minimum swaps to sort a array (https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/):
from collections import defaultdict def swaps(arr_e): vis = defaultdict(bool) ans = 0 j = 0 for i in range(len(arr_e)): if vis[i] or arr_e[i][0] == i: continue j = i cycles = 0 while not vis[j]: vis[j] = True j = arr_e[j][0] cycles += 1 if cycles > 0: ans += cycles - 1 return ans # Complete the lilysHomework function below. def lilysHomework(arr): arr_e = list(enumerate(arr)) arr_s = sorted(arr_e, key=lambda x: x[1]) ans1 = swaps(arr_s) arr_s = sorted(arr_e, key=lambda x: x[1], reverse = True) ans2 = swaps(arr_s) return min(ans1, ans2)
Seems like cookies are disabled on this browser, please enable them to open this website
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
I found another way to achieve the objective, this problem is very close to the minimum swaps problem, wich the objective is count the minimum swaps to sort a array (https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/):