关于“排序数列中元素出现次数问题”,这里采用折半法给出两种思路:
1、找到元素在数组中的一个索引位置,由于是数组是有序排列,所有在这个位置左右移动,就可以找出其所有出现的位置;
2、通过折半法找到元素的最大索引位置与最小索引位置,然后两个索引位置相减再加一,就是元素的出现的次数。
方法1中查找元素位置的方法复杂度为O(logn),左右遍历元素的复杂度为O(n),所以总的复杂度为O(logn) + k,其中k为元素出现的次数。
当n小,k大时不太适合用这种方法。
方法2中时间复杂度为O(logn),但是进行了两次查找,若n较大时也是一个不小的开。所以当n大,k小时,不太适合用这种方法。
/* * @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:需要查找的元素 * @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,减少一次折半过程,使得时间复杂度进一步减小。
/* * @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是最优的解法,适合各种情况,尤其在数组很大,元素出现的次数较多时,更能体现其优势~