所以這是這個函式，它有 2 個引數，即陣列和陣列的大小，我們必須以 的形式回傳答案Arraylist。我寫了這段代碼，但它給了我超出時間限制的錯誤，我在geeksforgeeks上解決了這個問題，但我不明白為什么它給出了超出時間限制的錯誤。謝謝！
public static ArrayList<Integer> duplicates(int arr[], int n) {
Arraylist<Integer> arrList = new ArrayList<>();
Arrays.sort(arr);
for(int i=0; i<n; i ) {
if(arr[i] == arr[i 1] && !arrList.contains(arr[i])) {
arrList.add(arr[i]);
}
}
if(arrList.isEmpty()) {
arrList.add(-1);
}
return arrList;
}
uj5u.com熱心網友回復：
我認為解決這個問題的預期時間復雜度是 o(n)，但是你使用了排序，這就是它的時間復雜度是 o(nlogn) 的原因。因此您可以使用 Treemap（按排序順序存盤值）以 o(n) 時間復雜度解決此問題。
class Solution {
public static ArrayList<Integer> duplicates(int arr[], int n) {
TreeMap <Integer,Integer> map= new TreeMap<>();
ArrayList <Integer> ans= new ArrayList<>();
for(int i=0;i<n;i ){
map.put(arr[i],map.getOrDefault(arr[i],0) 1);
}
for(int key : map.keySet()){
if(map.get(key)>1){
ans.add(key);
}
}
if (ans.size()==0){
ans.add(-1);
return ans;
}
return ans;
}
}
uj5u.com熱心網友回復：
您不需要排序，因為排序具有更高的復雜性O(nlog(n))。不知道這個問題的限制和說明是什么，但如果你真的沒有使用額外空間的問題，你可以使用另一個陣列串列，瀏覽所有元素arr并將其放入呼叫的某個串列temp并檢查是否號碼已經在temp. 代碼參考如下：
List<Integer> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int n = arr.length; // or you already passed n
for(int i=0;i<n;i ){
if(!temp.contains(arr[i])) {
temp.add(arr[i]);
}
else {
result.add(arr[i]);
}
}
return result;
這將在O(n) 時間和空間復雜度上完成。
當然，如果您想在不使用額外空間的情況下達到結果，則必須使用另一種方法。
uj5u.com熱心網友回復：
Condition肯定會在最后一個迭代步驟（when ）arr[i] == arr[i 1]期間導致例外，因為它將參考不存在的索引。你需要擺脫它。i=n-1100%i 1
contains()檢查 aList很昂貴，它具有O(n)時間復雜度。這會導致解決方案的整體二次O(n^2)時間復雜度。
正如@Scary Wombat在評論中指出的那樣，您可以使用它HashSet來檢查之前是否遇到過該元素。它還將消除對資料進行排序的需要，并且解決方案的時間復雜度將是線性的O(n)。
如果您有要求對結果進行排序，那么對結果串列進行排序會更有效（因為它包含的資料比給定陣列少）。
public static List<Integer> duplicates(int[] arr, int n) {
Set<Integer> seen = new HashSet<>();
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < n; i ) {
int next = arr[i];
if (!seen.add(next)) {
duplicates.add(next);
}
}
if (duplicates.isEmpty()) {
duplicates.add(-1);
}
// duplicates.sort(null); // uncomment this Line ONLY if results required to be in sorted order
return duplicates;
}
旁注：
- 不要使用具體
ArrayList的類，如回傳型別、變數型別、方法引數等。利用抽象，針對 , 等介面撰寫代碼List。Set如果編碼平臺希望您回傳一個ArrayList，那很不幸 - 將型別保留為是，但請記住，這不是要走的路。請參閱“編程到介面”是什么意思？ - 避免使用 C 風格的陣列宣告
int arr[]。因為它混合了變數名和型別，這可能看起來很混亂。int[] arr更可取。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505867.html