查找插入位置

我有一個整數ArrayList的整數。現在我有一個新的整數插入到ArrayList中。必須在適當的位置插入此新整數以保持ArrayList的排序順序。查找插入位置

我可以只添加整數，然後使用Collections.sort（ArrayList）進行排序，但由於ArrayList太大，這種排序需要時間，我需要多次插入，所以我不想結束多次分揀，這會耗盡我的時間。

Collections.sort（）具有O（nlogn）（使用歸併）。

我能有什麼耗時少，或者我可以手動搜索要插入的花費最少的時間位置？

時間是高優先級。

感謝提前:)

來源

2013-10-06 Sravan2023

爲什麼不乾脆在列表中，並在其適當的位置添加的元素。當你的list已經排序新list後insertion也將sorted，這將是一個O(N)操作。沒有必要一遍又一遍地對列表進行排序。

編輯： - 現在這裏有兩件事情。如果您需要查找要插入到當前列表中的元素的位置，則可以使用Binary Search。實際上，在該位置插入該元素將需要跟隨它的所有元素前移一個點爲插入元素創建空間，我認爲這比插入和重新排序更有效。

來源

2013-10-06 16:40:22 Prateek

實際上，我打算提出同樣的問題，但我不確定如果我們在這個問題上誤讀了一些東西... – icedwater

謝謝。那是一個很好的工作，這是170秒到115，但我需要幾乎到5秒。所以更有效率。 ?? – Sravan2023

您可以在'O（log N）'中找到元素必須使用'binary search'插入的位置複雜度 – Prateek

你可能要考慮使用不同的數據結構（如TreeSet如果可能的話），因爲將仍然會導致所有尾隨元素移位。您可以使用Collections.binarySearch雖則查找插入位置，它返回：

返回：搜索鍵的索引，如果它包含在列表中;否則，（ - （插入點） - 1）。插入點被定義爲鍵將被插入列表中的點：第一個元素的索引大於鍵，或者list.size（）（如果列表中的所有元素都小於指定的鍵）。請注意，這保證返回值將大於等於0當且僅當找到密鑰。

編輯：例與用List

List<Integer> numbers = new ArrayList<>(); 
private void add(int n) { 
    int idx = Collections.binarySearch(numbers, n); 
    if(idx < 0) { 
     idx += 1; 
     idx *= -1; 
    } 
    numbers.add(idx, n); 
} 

private void remove(int n) { 
    numbers.remove(n); 
}

來源

2013-10-06 16:47:27 Alowaniak

元素不是唯一的，所以不能使用TreeSet – Sravan2023

也可以解釋我如何使用二分查找。如果我有一個元素，並想知道它的位置，我可以使用二進制搜索。但在這裏我想知道插入的位置，所以我不明白我可以如何使用這個二進制搜索。如果我可以使用它會更有效。只是不明白我該怎麼做 – Sravan2023

如果你搜索的元素不在列表中（所以你添加的元素），它會返回'（ - （插入點）-1）'。我仍然認爲你會想要一個不同的數據結構，也許你可以使用'TreeMap'並且其值是元素的出現次數？ – Alowaniak

一個TreeMap

TreeMap<Integer, Integer> numbers = new TreeMap<>(); 
private void add(int n) { 
    if(numbers.containsKey(n)) 
     numbers.put(n, numbers.get(n)+1); 
    else 
     numbers.put(n, 1); 
} 

private void remove(int n) { 
    if(numbers.containsKey(n)) { 
     int i = numbers.get(n); 
     if(i == 1) 
      numbers.remove(n); 
     else 
      numbers.put(n, i-1); 
    } 
}

示例您可以使用自己的二進制搜索來估計新元素的位置，然後在良好的中置件

來源

2013-10-06 17:00:29 Sylwek

二進制搜索可用於查找列表中的現有元素。但是在這裏我需要找到要插入的位置。那麼我如何實現二進制搜索？ – Sravan2023

如果您使用'二進制搜索'來查找元素的位置，並且如果列表中沒有這個元素，二進制搜索可以返回最後一個搜索索引 - 它將是您的元素應該在哪裏估計的索引。然後你應該使用Inser Sort將你的元素放在正確的位置。例如：列表（1,2,3,4,6,7,8,9,10,11,12,13），你想把5列入列表二進制搜索將返回索引約3，然後你可以檢查'list.get（3）'是否大於或小於你的元素，並且使用插入排序的方式是右/左 – Sylwek

查找插入位置

回答

相關問題