問題描述：
你和彼得在談論
n電影，電影是用整數表示的[1,n]。您已根據自己的喜好為電影制作了排名串列。現在，彼得告訴你他的排名。你想知道你和彼得的品味有多相似。對于 2 部電影i, j，如果您和 Peter 都將電影排在電影i之前j，您將得到 11 的相似度。請輸出總相似度。
我知道我可以用蠻力的方式解決這個問題。它的Java代碼是這樣的：
int n = in.nextInt();
int[] rankingListOfMe = new int[n];
int[] rankingListOfPeter = new int[n];
int[] peterMovie2RankingIndex = new int[n 1];
for (int i = 0; i < n; i) rankingListOfMe[i] = in.nextInt();
for (int i = 0; i < n; i) {
rankingListOfPeter[i] = in.nextInt();
peterMovie2RankingIndex[rankingListOfPeter[i]] = i;
}
long similarity = 0L;
for (int i = 1; i < n; i) {
if (rankingListOfMe[i] == rankingListOfPeter[0]) continue;
int curJMovieIndex = peterMovie2RankingIndex[rankingListOfMe[i]];
for (int j = 0; j < i; j) {
if (peterMovie2RankingIndex[rankingListOfMe[j]] < curJMovieIndex) similarity ;
}
}
陣列rankingListOfXX是以電影排名為索引的陣列，它存盤電影id。ArraypeterMovie2RankingIndex為陣列，長度為n 1，索引為電影id，存盤對應的電影排名，通過電影id輕松獲取電影排名。每次我遍歷一個電影 id 時，我只計算有多少電影滿足請求。雖然這種方式可以解決問題，但我想知道是否有其他方法可以更有效地解決。上面演算法的時間復雜度是O(n^2)，這對我來說太多了。想了好久，不知道在哪里優化。我認為它與排序演算法有關，但我不知道如何使用排序演算法來解決這個問題。
uj5u.com熱心網友回復：
public void similarity(int[] me, int[] peter){
int[] peterTemp = new int[peter.length];
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < me.length; i ){
map.put(me[i], i);
}
for(int i = 0; i < peter.length; i ){
peterTemp[peterTemp.length - (i 1)] = map.get(peter[i]);
}
// as David Eisenstat pointed out we are going to count inversion in array, invCount method copied from here
// https://stackoverflow.com/questions/337664/counting-inversions-in-an-array
System.out.println(invCount(peterTemp));
}
long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i j] = right[j];
j ;
} else if (j == right.length) {
arr[i j] = left[i];
i ;
} else if (left[i] <= right[j]) {
arr[i j] = left[i];
i ;
} else {
arr[i j] = right[j];
count = left.length-i;
j ;
}
}
return count;
}
long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return invCount(left) invCount(right) merge(arr, left, right);
}
測驗：
for {1, 5, 6, 7} and {6, 7, 1, 5} result is 2
for {4, 7, 8, 3, 1, 2} and {3, 8, 7, 1, 2, 4} result is 7
解釋：?如果我們peterTemp像下面這樣構建：
peterTemp[i] = map.get(peter[i]);
對于每一個i, j這樣的，i > j我們peterTemp[i] >? peterTemp[j]
發現了一個相似之處。peterTemp我這樣構建peterTemp[peterTemp.length - (i 1)] = map.get(peter[i]);僅使用參考的代碼。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438326.html
上一篇：骰子的獨特組合
下一篇：Python集未檢測到重復節點