排序数列中元素出现次数问题 - 可酷可乐
可酷可乐发表于 2015-09-23 03:39:00
关于“排序数列中元素出现次数问题”，这里采用折半法给出两种思路：
1、找到元素在数组中的一个索引位置，由于是数组是有序排列，所有在这个位置左右移动，就可以找出其所有出现的位置；
2、通过折半法找到元素的最大索引位置与最小索引位置，然后两个索引位置相减再加一，就是元素的出现的次数。
方法1中查找元素位置的方法复杂度为O(logn)，左右遍历元素的复杂度为O(n)，所以总的复杂度为O(logn) + k，其中k为元素出现的次数。
当n小，k大时不太适合用这种方法。
方法2中时间复杂度为O(logn)，但是进行了两次查找，若n较大时也是一个不小的开。所以当n大，k小时，不太适合用这种方法。
方法1的PHP代码实现
/*
* @function:折半查找顺序数组中元素出现的位置
* @param:顺序排列的数组
* @param:要查找的元素
* @param: true 查找最大位置， false查找最小位置
* @return:返回元素的位置索引，没有返回零
*/
function arr_index_value($arr, $num, $flag){
$left = 0;
$right = count($arr) - 1;
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
//若$flag为真，获得最大索引位置
if(!$flag){
if($mid == 0 || $arr[$mid-1] != $num) return $mid;
$right = $mid - 1;
}
//若$flag为假，获得最小索引位置
else{
if($mid == $right || $arr[$mid+1] != $num) return $mid;
$left = $mid + 1;
}
}
}
}
* @function:折半查找顺序数组中元素出现的位置
* @param:顺序排列的数组
* @param:要查找的元素
* @param: true 查找最大位置， false查找最小位置
* @return:返回元素的位置索引，没有返回零
*/
function arr_index_value($arr, $num, $flag){
$left = 0;
$right = count($arr) - 1;
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
//若$flag为真，获得最大索引位置
if(!$flag){
if($mid == 0 || $arr[$mid-1] != $num) return $mid;
$right = $mid - 1;
}
//若$flag为假，获得最小索引位置
else{
if($mid == $right || $arr[$mid+1] != $num) return $mid;
$left = $mid + 1;
}
}
}
}
方法2的PHP代码实现：
/*
* @function:折半查找有序数组中某元素出现的次数。
* 思路：分别找到元素在数组中出现的最大索引位置与最小索引位置，
* 然后两个相减，再加一就是出现的次数。
* @param:顺序排列的有序数组
* @param:需要查找的元素
* @return:元素出现的次数，若不存在则返回零
*/
function arr_count_values2($arr, $num){
//最大索引位置 - 最小索引位置 + 1
$max = arr_index_value($arr, $num, true);
$min =arr_index_value($arr, $num, false);
if($max == 0) return 0;
return $max - $min + 1;
}
/*
* @function:折半查找顺序数组中元素出现的位置
* @param:顺序排列的数组
* @param:要查找的元素
* @param: true 查找最大位置， false查找最小位置
* @return:返回元素的位置索引，没有返回零
*/
function arr_index_value($arr, $num, $flag){
$left = 0;
$right = count($arr) - 1;
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
//若$flag为假，获得最小索引位置
if(!$flag){
if($mid == 0 || $arr[$mid-1] != $num) return $mid;
$right = $mid - 1;
}
//若$flag为真，获得最大索引位置
else{
if($mid == $right || $arr[$mid+1] != $num) return $mid;
$left = $mid + 1;
}
}
}
}
//测试
$a = array(1, 2, 2, 2, 3, 3, 5, 8);
print arr_count_values2($a, 2);
* @function:折半查找有序数组中某元素出现的次数。
* 思路：分别找到元素在数组中出现的最大索引位置与最小索引位置，
* 然后两个相减，再加一就是出现的次数。
* @param:顺序排列的有序数组
* @param:需要查找的元素
* @return:元素出现的次数，若不存在则返回零
*/
function arr_count_values2($arr, $num){
//最大索引位置 - 最小索引位置 + 1
$max = arr_index_value($arr, $num, true);
$min =arr_index_value($arr, $num, false);
if($max == 0) return 0;
return $max - $min + 1;
}
/*
* @function:折半查找顺序数组中元素出现的位置
* @param:顺序排列的数组
* @param:要查找的元素
* @param: true 查找最大位置， false查找最小位置
* @return:返回元素的位置索引，没有返回零
*/
function arr_index_value($arr, $num, $flag){
$left = 0;
$right = count($arr) - 1;
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
//若$flag为假，获得最小索引位置
if(!$flag){
if($mid == 0 || $arr[$mid-1] != $num) return $mid;
$right = $mid - 1;
}
//若$flag为真，获得最大索引位置
else{
if($mid == $right || $arr[$mid+1] != $num) return $mid;
$left = $mid + 1;
}
}
}
}
//测试
$a = array(1, 2, 2, 2, 3, 3, 5, 8);
print arr_count_values2($a, 2);
我们可以进一步优化方法2，减少一次折半过程，使得时间复杂度进一步减小。
方法3的PHP实现代码：
/*
* @function:折半查找有序数组中某元素出现的次数。
* 思路：分别找到元素在数组中出现的最大索引位置与最小索引位置，
* 然后两个相减，再加一就是出现的次数。
* @param:顺序排列的有序数组
* @param:需要查找的元素
* @return:元素出现的次数，若不存在则返回零
*/
function arr_count_values3($arr, $num){
$left = 0;
$right = count($arr) - 1;
//折半法获得元素一位置
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
break;
}
}
if($left > $right) return 0;
$mid_t = $mid;
$left_t = $left;
$right_t = $right;
//折半法获得最小索引位置
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($mid == 0 || $arr[$mid-1] != $num){
$min = $mid;
break;
}
$right = $mid - 1;
}
//折半法获得最大索引位置
while($left_t <= $right_t){
$mid_t = (int)(($left_t + $right_t)/2);
if($mid_t == $right_t || $arr[$mid_t+1] != $num){
$max = $mid_t;
break;
}
$left_t = $mid_t + 1;
}
//元素出现次数 = 最大索引位置 - 最小索引位置 + 1
$max = arr_index_value($arr, $num, true);
$min =arr_index_value($arr, $num, false);
return $max - $min + 1;
}
* @function:折半查找有序数组中某元素出现的次数。
* 思路：分别找到元素在数组中出现的最大索引位置与最小索引位置，
* 然后两个相减，再加一就是出现的次数。
* @param:顺序排列的有序数组
* @param:需要查找的元素
* @return:元素出现的次数，若不存在则返回零
*/
function arr_count_values3($arr, $num){
$left = 0;
$right = count($arr) - 1;
//折半法获得元素一位置
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($arr[$mid] > $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须加一付给$right
$right = $mid - 1;
}else if($arr[$mid] < $num){
//注意为了在所有情况下$mid值能随着while循环朝着某个方向变化，$mid必须减一付给$left
$left = $mid + 1;
}else{
break;
}
}
if($left > $right) return 0;
$mid_t = $mid;
$left_t = $left;
$right_t = $right;
//折半法获得最小索引位置
while($left <= $right){
$mid = (int)(($left + $right)/2);
if($mid == 0 || $arr[$mid-1] != $num){
$min = $mid;
break;
}
$right = $mid - 1;
}
//折半法获得最大索引位置
while($left_t <= $right_t){
$mid_t = (int)(($left_t + $right_t)/2);
if($mid_t == $right_t || $arr[$mid_t+1] != $num){
$max = $mid_t;
break;
}
$left_t = $mid_t + 1;
}
//元素出现次数 = 最大索引位置 - 最小索引位置 + 1
$max = arr_index_value($arr, $num, true);
$min =arr_index_value($arr, $num, false);
return $max - $min + 1;
}
可见，方法3是最优的解法，适合各种情况，尤其在数组很大，元素出现的次数较多时，更能体现其优势~
本文链接：排序数列中元素出现次数问题，转载请注明。