h******o
发帖数: 334 | 1 一个只是column sorted的2D array,用binary search查找一个element出现的次数。
多谢帮助！
public static int count(int[][] array, int query) {
int searchTotal = 0;
for (int c=0; c < array.length; c++){
searchTotal += biSearch(array, query, c);
}
return searchTotal;
}
private static int biSearch(int[][] array, int query, int row) {
// create a 1D array to hold the entries of 2D array's column
int[] column = new int[array.length];
int count =0;
int low = 0;
int high = column.length - 1;
// put 2D array's column into 1D array
for (int i = 0; i < array.length; i++)
column[i] = array[i][row];
// binary search on column array
while (low <= high) {
int mid = low + (high - low) / 2;
if (column[mid] > query){
high = mid - 1;
}
else if (column[mid] < query){
low = mid + 1;
}
else if (column[mid] == query) {
count++;
int left = -1;
int right = 1;
while ((mid + left) >= 0) {
if (column[mid + left] == query) {
left--;
count++;
}
}
while ((mid + right) <= (column.length - 1)) {
if (column[mid + right] == query) {
right++;
count++;
}
}
//return count;
}
}
return count;
} | s********r
发帖数: 394 | 2 程序写的很糟糕，biSearch应该只完成数组的搜索，传入数组为什么搞成二维的？
★ 发自iPhone App: ChineseWeb 8.7
【在 h******o 的大作中提到】
: 一个只是column sorted的2D array,用binary search查找一个element出现的次数。
: 多谢帮助！
: public static int count(int[][] array, int query) {
:
: int searchTotal = 0;
: for (int c=0; c < array.length; c++){
: searchTotal += biSearch(array, query, c);
: }
:
: return searchTotal;
| w***g
发帖数: 5958 | 3 错的地方好几个。第一个colum/row不分。最外层c的循环应该是到array[0].length而不
是array.length
biSearch这种程序需要背一个标准的。检测到相等时处理就完全混乱了。
正确的做法：检测到相等把low置为mid（或者把high置为mid)，并且接着找，直到low和
high相等为止。最后low = high就是第一个>=query的数（或者第一个<=query的数)。然
后线性往一个方向找。
【在 h******o 的大作中提到】
: 一个只是column sorted的2D array,用binary search查找一个element出现的次数。
: 多谢帮助！
: public static int count(int[][] array, int query) {
:
: int searchTotal = 0;
: for (int c=0; c < array.length; c++){
: searchTotal += biSearch(array, query, c);
: }
:
: return searchTotal;
| h******o
发帖数: 334 | 4 多谢回复！ 我的想法是把二维数组的column的elements导入到一维数组，然后binary
search这个一维数组，不知这样的转换是否可行？
【在 s********r 的大作中提到】
: 程序写的很糟糕，biSearch应该只完成数组的搜索，传入数组为什么搞成二维的？
:
: ★ 发自iPhone App: ChineseWeb 8.7
| h******o
发帖数: 334 | 5 非常感谢！ 我再想想你说的怎么实现。。。
而不
low和
。然
【在 w***g 的大作中提到】
: 错的地方好几个。第一个colum/row不分。最外层c的循环应该是到array[0].length而不
: 是array.length
: biSearch这种程序需要背一个标准的。检测到相等时处理就完全混乱了。
: 正确的做法：检测到相等把low置为mid（或者把high置为mid)，并且接着找，直到low和
: high相等为止。最后low = high就是第一个>=query的数（或者第一个<=query的数)。然
: 后线性往一个方向找。
|
|
