我有一個使用java的33000個元素的排序數組列表,我怎樣才能列出以子串開頭的元素。如何查找以排序的ArrayList中的子字符串開頭的元素?
例如: 我有一個字符串「空氣」。因此,我需要以「空氣」(「飛機」,「空軍」,「航空公司」等)開頭的每一個字
有沒有辦法做到這一點,而不是一個接一個迭代?
我有一個使用java的33000個元素的排序數組列表,我怎樣才能列出以子串開頭的元素。如何查找以排序的ArrayList中的子字符串開頭的元素?
例如: 我有一個字符串「空氣」。因此,我需要以「空氣」(「飛機」,「空軍」,「航空公司」等)開頭的每一個字
有沒有辦法做到這一點,而不是一個接一個迭代?
所以,給你一個整理ArrayList<String>
words
,你可以這樣做:
String prefix = "air";
int start = Collections.binarySearch(words, prefix);
// index of prefix OR -(insertion point) - 1
if (start < 0) // prefix is not contained as a whole word
start = -start - 1;
int end = start;
while (end < words.size() && words.get(end).startsWith(prefix))
end++;
List<String> prefixWords = words.subList(start, end);
二進制搜索O(log(N))
及切分是O(K)
其中K
是子表中的「空氣」的長度(數字 - 前綴詞)。所以,這應該比遍歷列表好得多,至少在不同的前綴上分割(最壞的情況是所有的單詞都以前綴開頭)。
什麼是結束?是我的arrayList的結束索引? –
更新了它。 'end'是子列表的結束索引(獨佔)。 – schwobaseggl
如果您不知道以「air」開頭的元素數目,則您的搜索將按照O(n)的順序進行。沒有蠻力方法或平衡樹搜索,您可以執行以小於O(n)達到此目的。
二進制搜索將成爲第一轉到像
public static int binarySearch(ArrayList<String> sortedArray,String find){
int lowerBound=0;
int upperBound=sortedArray.size()-1;
while(true){
int midIndex=lowerBound+((upperBound-lowerBound)/2);
String curr=sortedArray.get(midIndex);
if(upperBound<lowerBound){
System.out.println("word not found");
return -1;
}
if (curr.equals(find))
return midIndex;
if(curr.compareTo(find)>0)
upperBound=midIndex-1;
if(curr.compareTo(find)<0)
lowerBound=midIndex+1;
}
}
然後你得到了指數迭代之後在朝着左邊的列表中,右,直到你打表的結束/開始或者從一個您選擇不同的前綴搜索爲
public static ArrayList<String> makeList(ArrayList<String> sortedArray,String startingWith){
ArrayList<String> result=new ArrayList<>();
ArrayList<String> temp=new ArrayList<>(sortedArray.size());
for(int i=0;i<sortedArray.size();i++){
temp.add(" ");
}
//copy sortedArray to temp
for(String s: sortedArray){
if(s.length()>startingWith.length()) {
temp.set(sortedArray.indexOf(s), s.substring(0, startingWith.length()));
} else temp.set(sortedArray.indexOf(s),s);
}
int index=binarySearch(temp,startingWith);
result.add(sortedArray.get(index));
int leftIndex=index;
int rightIndex=index;
while(true){
//if left and right index dont go out of bounds cont. iterating
if ((leftIndex - 1) >= 0) leftIndex--;
if ((rightIndex + 1) < sortedArray.size()) rightIndex++;
//if left and right index are at end of list return
if((rightIndex>=sortedArray.size()) && (leftIndex<0)) return result;
boolean isLeft;
boolean isRight;
if(sortedArray.get(leftIndex).length()>startingWith.length()) {
isLeft = sortedArray.get(leftIndex).substring(0,startingWith.length()).equals(startingWith);
}else isLeft=false;
if(sortedArray.get(rightIndex).length()>startingWith.length()) {
isRight = sortedArray.get(rightIndex).substring(0,startingWith.length()).equals(startingWith);
}else isRight=false;
if(!isLeft && !isRight) return result;
if(isRight) result.add(sortedArray.get(rightIndex));
if(isLeft) result.add(sortedArray.get(leftIndex));
}
}
是的,有多種方式。你試過什麼了 ? – Rehman
如果列表沒有排序,那麼它將涉及迭代整個列表! – schwobaseggl
For循環與正則表達式模式,但我在另一個循環內使用它。因此,正在爲每個循環做大搜索... –