在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


LeetCode #35 搜索插入位置

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

解题思路

题目的任务: 在一个 已排序的数组 中找到目标值的位置。

思路:
从头到尾逐个对元素进行比较。

  1. 当前元素等于目标元素时,返回当前元素下标。
  2. 当前元素大于目标元素时,即目标元素位置在当前元素的前面,所以当前元素需要右移让出位置,返回的仍然时当前下标。
  3. 遍历完整个数组时,说明目标元素比所有的元素都要大,所以返回最后一个元素下标加一,即 nums.length

代码:

class Solution {
public int searchInsert(int[] nums, int target) {
int length = nums.length;
for (int i = 0; i < length; i++){
if (nums[i] >= target) return i;
}

// 遍历完整个数组仍没有找到符合元素,则目标元素比所有元素都要大
return length;
}
}

改进思路:
如果数组非常大,则最坏的情况需要对整个数组进行比较。避免这种情况,我们可以在遍历前找出目标元素可以能存在的范围。

  1. 先取数组中间的元素进行比较。
  2. 如果大于目标元素,则范围在 [0,mid]。如果小于目标元素,则范围在 [mid-1, length-1]。
  3. 这样,需要遍历的元素就减少了一半了。

改进代码:

class Solution {
public int searchInsert(int[] nums, int target) {
int length = nums.length;
int left = 0, right = length - 1;
int mid = (left + right)/2;

// 判断范围
if (nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}

for (int i = left; i <= right; i++){
if (nums[i] >= target) return i;
}

// 遍历完整个数组仍没有找到符合元素,则目标元素比所有元素都要大
return length;
}
}

二分查找思路:
其实上面的思路就是二分查找,当我们将范围缩小到只有一个元素的时候,答案自然就出来了。

二分查找代码:

class Solution {
public int searchInsert(int[] nums, int target) {
int length = nums.length;
int left = 0, right = length - 1;
int mid = (left + right)/2;

while(left != right){
if (nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
mid = (left + right)/2;
}

if (nums[right] >= target) return right;

return right + 1;
}
}

评论