南宁市建设信息网站,南通网站的优化,dw旅游网站模板,企业邮箱入口目录
面试题 68 : 查找插入位置
面试题 69 : 山峰数组的顶部 面试题 68 : 查找插入位置
题目#xff1a;
输入一个排序的整数数组 nums 和一个目标指 t#xff0c;如果数组 nums 中包含 t#xff0c;则返回 t 在数组中的下标#xff1b;如果数组 nums 中不包含 t#…目录
面试题 68 : 查找插入位置
面试题 69 : 山峰数组的顶部 面试题 68 : 查找插入位置
题目
输入一个排序的整数数组 nums 和一个目标指 t如果数组 nums 中包含 t则返回 t 在数组中的下标如果数组 nums 中不包含 t则返回将 t 按顺序插入数组 nums 中的下标。假设数组中没有相同的数字。例如输入数组 nums 为 [1, 3, 6, 8]如果目标值 t 为 3则输出 1如果 t 为 5则返回 2。
分析
首先考虑如果目标值 t 不在数组中时它应该被插入哪个位置。由于数组是排序的因此它应该排在所有比它小的数字的后面。也就是说它的插入位置满足两个条件一是该位置上的数字大于 t二是该位置的前一个数字小于 t总结下来就是数组中第一个大于 t 的数字的位置。例如当数组为 [1, 3, 6, 8]目标值为 5它将被插入下标为 2 的位置该位置当前的值为 6大于目标值该位置的前一个值是 3小于目标值。
当数组中包含目标值时返回它在数组中的位置。
综上所述即查找数组中第一个大于或等于 t 的数字的位置。
代码实现
class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size() - 1;while (left right){int mid (left right) / 2;if (nums[mid] target)left mid 1;else // nums[mid] targetright mid - 1;}return left;}
}; 当 while 循环结束left rightleft 左边的数字都小于 targetright 右边的数字都大于或等于 target因此 right 1即 left 就是第一个大于或等于 target 的数字的位置。 面试题 69 : 山峰数组的顶部
题目
符合下列属性的数组 arr 称为山峰数组 arr.length 3 存在 i0 i arr.length - 1 使得arr[0] arr[1] ··· arr[i - 1] arr[i] arr[i 1] ··· arr[arr.length - 1]
给定由整数组成的山峰数组 arr返回下标 i即山峰顶部数组中最大值的位置。
例如在数组 [1, 3, 5, 4, 2] 中最大值是 5输出它在数组中的下标 2。
分析
不难想到直观的解法来解决这个题目即逐一扫描整个数组通过比较就能找出数组中的最大值。显然这种解法的时间复杂度是 O(n)。这种解法对任意数组都适用并没有充分利用这个题目的特点即数组先递增再递减。由于问题是关于在排序数组中查找数字虽然整个数组并不是排序的但分成前后两段后每段都分别排序因此二分查找算法值得一试。
山峰数组中的最大值是数组中唯一一个比它左右两边数字都大的数字。位于最大值前面的数字除第 1 个数字之外总是比它前一个数字大但比它后一个数字小位于最大值后面的数字除最后一个数字之外总是比它前一个数字小但比它后一个数字大。
可以根据山峰数组的这个特点应用二分查找算法。先取出数组中间的数字。 如果这个数字比它前后两个数字都大那么就找到了数组的最大值。 如果这个数字比它前一个数字大但比后一个数字小那么这个数字位于数组递增的部分数组的最大值一定在它的后面接下来只需要在数组的后半部分查找就可以。 如果这个数字比它前一个数字小但比后一个数字大那么这个数字位于数组递减的部分数组的最大值一定在它的前面接下来只需要在数组的前半部分查找就可以。
代码实现
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left 1;int right arr.size() - 2;while (left right){int mid (left right) / 2;if (arr[mid] arr[mid - 1] arr[mid] arr[mid 1])return mid;if (arr[mid] arr[mid - 1])left mid 1;elseright mid - 1;}return -1;}
}; 注意 在一个长度为 n 的山峰数组中由于第 1 个数字和最后一个数字都不可能是最大值因此初始查找范围为数组下标从 1 到 n - 2 的部分。 如果输入的数组是一个有效的山峰数组那么 while 循环中一定能找到山峰数组的最大值。只是 C 的语法要求函数的每个分支必须有返回值所以在函数体的最后添加一行返回 -1 的代码。实际上这一行代码不会被执行。
