我有兩個陣列陣列 a = [1, 2, 3, 4, 5]和陣列 b = [6, 5, 4, 3, 2]并且我回傳一個陣列串列，其中包含一個計數，我在其中獲取陣列的元素b并檢查陣列 a的哪些元素大于或等于陣列 b的每個元素，我將其存盤在count變數中，然后將每個計數添加到串列中，因此輸出將為list = [0, 1, 2 , 3, 4]，但是我撰寫的代碼在更大的輸入集上缺乏性能，并且沒有以預期的方式給出假設的答案 關于如何改進我的代碼以提高性能的任何想法
static List<Integer> giantArmy(int a[],int b[]){
List<Integer> list = new ArrayList<Integer>();
if (a.length == 1 && a[0] == 0) {
list.add(0);
return list;
}
int count = 0;
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < a.length; j ) {
if (a[j] >= b[i]) {
count ;
}
}
list.add(count);
count = 0;
}
return list;
}
uj5u.com熱心網友回復：
Basil Bourque 評論的實作。這是O(n log n). （排序是O(n log n)和二分查找O(log n)重復n次數）
static List<Integer> giantArmy(int a[],int b[]){
int aLength = a.length;
List<Integer> result = new ArrayList<>();
Arrays.sort(a);
for (int i : b) {
int index = Arrays.binarySearch(a, i);
if (index < 0)
index = -index - 1;
result.add(aLength - index);
}
return result;
}
public static void main(String[] args) {
System.out.println(giantArmy(new int[] {1, 2, 3, 4, 5}, new int[] {6, 5, 4, 3, 2}));
}
輸出：
[0, 1, 2, 3, 4]
n對 sorted 進行二分搜索會a產生a其找到的位置右側的元素數大于或等于 的元素數n。
[1 2 3 4 5]
(number of elements >= 6) = 0
x (number of elements >= 5) = 1
x x (number of elements >= 4) = 2
x x x (number of elements >= 3) = 3
x x x x (number of elements >= 2) = 4
x x x x x (number of elements >= 1) = 5
x x x x x (number of elements >= 0) = 5
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/527763.html
標籤：爪哇数组列表for循环