题干
给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-insert-position
既然是有序数组,那就尽量少的遍历,多用判断来搞定,这样会比较快
PHP 实现:
function searchInsert($nums, $target) {
$count = count($nums);
for ($i = 0; $i < $count; $i++) {
if (isset($nums[$i + 1]) && $nums[$i] < $target && $target <= $nums[$i +1]) {
return $i + 1;
}
if (!isset($nums[$i + 1]) && $nums[$i] < $target) {
return $i + 1;
}
if ($nums[$i] >= $target) {
return 0;
}
}
}
return searchInsert([1,3,5,6], 5); // output: 2
二分法解题思路
一般使用 二分查找 都需要先对原数组进行排序,题中给到的数组是已经排序的,因此这一步可以省去。
二分查找 思路比较简单,首先初始化三个指针: left 指向 nums 最左边的元素,right 指向 nums 右边的元素,根据 left 和 right 计算 mid 指针。我们先拿目标值 target 与 nums [mid] 进行比较。
如果 target > nums[mid],说明要查找的值有可能在 nums[mid+1, right] 之间,这时候将 left 赋值为 mid + 1,right 不变,重新计算一下 mid,重新比较。
如果 target < nums[mid],说明要查找的值有可能在 nums[left, mid-1] 之间,这时候将 right 赋值为 mid - 1,left 不变,重新计算一下 mid,重新比较。
如果 target == nums[mid],那么恭喜找到啦,根据题意,找到的索引值就是 target 插入的目标位置,即返回 mid 即可。
如果 二分查找 结束仍是没有找到 target 的值,最后返回 left 就可以了,至于为什么 left 的值是 target 插入的位置,可以看流程图的分析。
mid 的计算方式: mid = left + (rigth - left) / 2,至于为什么不用 ( left + right ) / 2 来计算 mid 是因为 right + left 有可能溢出。 注: (right - left) / 2 取整,因为数组的索引值是整数。
———————————————— 原文作者:三斤和他的喵 转自链接:https://learnku.com/articles/43723#reply139614
PHP 实现V2 二分法查找
function searchInsert($nums, $target) :int {
if (count($nums) <= 0) {
return 0;
}
$left = 0;
$right = count($nums) - 1;
while ($left <= $right) {
// 根据 left 和 right 计算 mid 的值
$mid = $left + ($right - $left) / 2; // ( left + right ) / 2
// 目标值大于中间值,left = mid + 1
if ($nums[$mid] < $target) {
$left = $mid + 1;
// 目标值小于中间值 right = mid - 1
} else if ($nums[$mid] > $target) {
$right = $mid - 1;
} else {
// 目标值等于中间值返回 mid,即为目标值需要插入的位置
return $mid;
}
}
// 找不到目标值,这时候返回left就是目标值需要插入的位置
return $left;
}
return searchInsert([1,4,5,7], 3); // output:1