java查找排序数组中重复值的计数
我只是想知道这段代码是否可以进一步改进。这是一个简单的类,它接受排序数组和值作为参数,并尝试查找该值在数组中出现的次数
据我所知,代码的复杂度是O(logn+k)[假设k是n的子集]。这个代码可以进一步改进吗
public class SearchSortedArray {
// Find number count in an array. Total Complexity = O(log n + k) [assuming k is the subset of n]
public static int findNumberCountInAnArray(List<Integer> array, Integer findValue) {
//Search Index
Integer searchIndex = findIndex(array, findValue, 0);
//Find Count
return countArray(array, searchIndex);
}
// Search Index. Complexity = O(log n)
private static Integer findIndex(List<Integer> array, Integer findValue, int offset) {
if(array.size() == 0) {
return null;
}
if(findValue < array.get(array.size()/2)) {
return findIndex(array.subList(0, array.size()/2), findValue, 0);
} else if(findValue > array.get(array.size()/2)) {
offset = offset + array.size()/2;
return findIndex(array.subList(array.size()/2, array.size()), findValue, offset);
}
return array.size()/2+offset;
}
// Find count. Complexity = O(k) [assuming k is the subset of n]
private static int countArray(List<Integer> array, Integer searchIndex) {
if(null == searchIndex) {
return 0;
}
Integer searchValue = array.get(searchIndex);
Integer searchIndexStore = searchIndex;
int count = 0;
while(searchIndex < array.size() && searchValue == array.get(searchIndex)) {
count++;
searchIndex++;
}
searchIndex = searchIndexStore;
while(searchIndex > 0 && searchValue == array.get(searchIndex-1)) {
count++;
searchIndex--;
}
return count;
}
}
这是主课
// Test main class.
public class TestMain {
public static void main(String[] args) {
Integer[] sample1 = {1, 1, 1, 2, 3, 4, 4, 4, 4, 5, 5, 5};
ArrayList<Integer> arraySample1 = new ArrayList<Integer>(Arrays.asList(sample1));
// Find the number of times 5 is repeated in the array?
System.out.println(SearchSortedArray.findNumberCountInAnArray(arraySample1, 5));
Integer[] sample2 = {1, 1, 2, 3, 3, 4, 5, 8, 8, 9, 9, 10, 10, 14, 18};
ArrayList<Integer> arraySample2 = new ArrayList<Integer>(Arrays.asList(sample2));
// Find the number of times 10 is repeated in the array?
System.out.println(SearchSortedArray.findNumberCountInAnArray(arraySample2, 10));
}
}
谢谢
# 1 楼答案
使用两种方法代替一种二进制搜索:
findValue
的第一次出现。让我们称之为索引lo
。我相信这就是你的findIndex
函数所做的李>findValue
的值,或者n
如果不存在这样的值。让我们称之为索引hi
李>现在结果是
hi - lo
运行时:O(日志n)。请注意,如果k的预期值很小,即在log(n)的小常数因子内,那么您的代码实际上可能会更好,因为线性搜索比二进制搜索更高效