要求：有一個輸入串列和一個輸入班次號。第一行包含兩個以空格分隔的整數，表示：
- n，整數個數，和
- d，要執行的左旋轉次數。
第二行包含描述arr[]的以空格分隔的整數。
約束
- 1 <= n <= 10^5
- 1 <= d <= n
- 1 <= arr[i] <= 10^6
樣本輸入
- 5 , 4
- 1 2 3 4 5
樣本輸出
5 1 2 3 4
我撰寫了這段代碼，它作業正常，但在大型操作時超時。所以我需要優化我的代碼來成功運行所有的測驗用例。如何實作。
public static List<Integer> rotateLeft(int d, List<Integer> arr) {
int size = arr.size();
while(d>0) {
int temp = arr.get(0);
for(int i = 0; i<size; i ){
if(i != size-1){
arr.set(i,arr.get(i 1));
} else {
arr.set(i,temp);
}
}
d--;
}
return arr;
}
此輸入失敗：
- n = 73642
- d = 60581
- 還有一個大小為 73642 的巨大整數串列。
uj5u.com熱心網友回復：
這可以在一個回圈中完成，而不是使用嵌套回圈。i移位后索引處元素的最終索引n可以計算為(i n) % listLength，該索引可用于填充移位串列。像這樣：
import java.util.*;
class HelloWorld {
public static void main(String[] args) {
List<Integer> arr = Arrays.asList(1,2,3,4,5);
System.out.println(rotateLeft(4, arr));
}
public static List<Integer> rotateLeft(int d, List<Integer> arr) {
List<Integer> rotatedList = new ArrayList<>(arr.size());
int i=0;
for(i=0; i< arr.size(); i ) {
int rotatedElementIndex = ((i d) % arr.size());
rotatedList.add(arr.get(rotatedElementIndex));
}
return rotatedList;
}
}
uj5u.com熱心網友回復：
從來不喜歡hackerrank謎題。“和一個巨大的整數陣列”是什么意思？我們可以創建一個新串列還是需要修改現有串列？如果我們應該修改現有的，為什么我們的方法不是無效的？
如果我們可以創建新串列，最佳解決方案將是創建新的 Integer[] 陣列并呼叫 System.arraycopy() 兩次。
如果進行行內修改，解決方案是：
public static List<Integer> rotateLeft(int d, List<Integer> arr) {
int i = 0, first = arr.get(0);
int n = arr.size();
while (true) {
int source = (i d) % n;
if (source == 0) {
arr.set(i, first);
break;
}
arr.set(i, arr.get(source));
i = source;
}
return arr;
}
uj5u.com熱心網友回復：
對于就地解決方案：
反轉子陣列
arr[0, d)并arr[d, n)就地。這是通過交換對稱對中的元素來完成的。反轉整個陣列。
例如abcdefghijk，d=4
abcd|efghijk -> dcba|kjihgfe -> efghijk|abcd
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/496603.html
上一篇：如何使用演算法遍歷圖