34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
给定一个排序好的列表，返回给定某数值在数组内的其实，和终点下标。
如果没有找到就返回[-1,-1]
控制时间复杂度位O(log n)。
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
存在该元素的话，返回下标的范围
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
没有该元素的话返回[-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
为空的话就返回[-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array. 数组是一个非递减类数组
-109 <= target <= 109
思考
从题目给的时间复杂度要求来看，这又是一道需要二分法进行查找的题目。
从给的例子来看，有几个先决条件。
- 数组为空，或者找不到目标的时候返回[-1,-1]。
- 如果数组中只包含一个目标的时候应该返回一样的元素。[a,a]
我觉得我们可以每次找到一个目标元素的下标的时候，通过比较找出min和max最后填入return中。但是在比较最小的时候要注意有-1的存在，所以在比较最小的时候应该先判断是否有-1，并将其排除在外。
class Solution:
def min_ex(self, n1, n2):
if n1==-1:
return n2
if n2==-1:
return n1
return min(n1, n2)
def searchRange(self, nums: List[int], target: int) -> List[int]:
ret = [-1,-1]
l_nums = len(nums)
if not l_nums:
return ret
sp = int(l_nums/2)
if nums[sp] == target:
ret[0] = self.min_ex(sp, ret[0])
ret[1] = max(sp,ret[1])
ret1 = self.searchRange(nums[:sp], target)
ret[0] = self.min_ex(ret1[0], ret[0])
ret[1] = max(ret1[1],ret[1])
ret1 = self.searchRange(nums[sp+1:], target)
if ret1[0]!=-1:
ret1[0]+=sp+1
if ret1[1]!=-1:
ret1[1]+=sp+1
ret[0] = self.min_ex(ret1[0], ret[0])
ret[1] = max(ret1[1], ret[1])
return ret
先定义了一个函数来判定最小值。然后是对函数进行了递归处理 (原本想用迭代的。。结果写着写着就写成了递归。。就很无语)。
在这道题目里面，其实和33题LeetCode33. Search in Rotated Sorted Array很像，就是多了一步对-1的判定。
答案解析
二分法
int binarySearch(int* nums, int numsSize, int target, bool lower) {
int left = 0, right = numsSize - 1, ans = numsSize;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int leftIdx = binarySearch(nums, numsSize, target, true);
int rightIdx = binarySearch(nums, numsSize, target, false) - 1;
int* ret = malloc(sizeof(int) * 2);
*returnSize = 2;
if (leftIdx <= rightIdx && rightIdx < numsSize && nums[leftIdx] == target && nums[rightIdx] == target) {
ret[0] = leftIdx, ret[1] = rightIdx;
return ret;
}
ret[0] = -1, ret[1] = -1;
return ret;
}
这里用的就是迭代的方式。基本思路和我的一致。
思考
迭代和递归的理解
迭代就是循环，通过循环处理问题，并定义好合适的返回条件。
递归是将复杂的问题分为一小部分，每次只对一小部分进行处理，并在每次对递归的返回值进行有效的处理。可将它分为以下两类。
1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
2)回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.
两者之间的关系：
1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
2） 能用迭代的不用递归,递归调用函数,计算有重复,浪费空间,并且递归太深容易造成堆栈的溢出.说明还是迭代好。
从这道题目来看，答案给出的迭代，是每次对下标进行二分法的更新。然后最后找到合适的下标。返回并进行判断。
。。迭代好难理解突然之间觉得。。直接摆烂吧要不。但是下次接着努力学会如何使用迭代
