一、数组理论基础
- 数组下标都是从0开始的
- 数组内存空间的地址是连续的
- 数组的元素是不能删的，只能覆盖
二、刷题
第一题 704.二分查找
题目链接：https://leetcode.com/problems/binary-search/
难度：easy
思路：
题干sorted ascending array ，再加上给一个target返回符合的索引，很显然是需要缩小查找范围——首选二分查找法
再看限制条件，nums长度，时间复杂度最多为O(n^2), 如果用二分查找时间复杂度是O(logn) 符合题目条件
代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
# sorted array - BS 目的：缩小查找范围
# l, r
l=0
r=len(nums)
while l<r:
m = l + (r - l)//2
if nums[m] == target:
return m
elif nums[m]>target:
r = m
else:
l = m+1
return -1
习惯写左闭右开的方法，l<r, 其中r是不可能被遍历到的位置。
时间复杂度：O（logn)
空间复杂度：O（1）
第二题 34.有序数组找首位末位
题目链接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
难度：medium
思路：
non-decreasing order-BS，target
又要求O(log n) ----二分查找
这道题的难点在于：如何确定下边界和上边界，怎么缩小范围，初刷没做出来，看答案看懂的。
代码：
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
#non-decreasing order-BS，target，lower bound & upper bound
#O(log n) ---- 100% BS solution
''''while l<r:
if nums[m]>target:
r=m
if nums[m]<target:
l=m+1
if nums[m]==target:
l+=1
r-=1
#这道题的难点在于：如何确定下边界和上边界，怎么缩小范围
return [-1,-1]'''
def search(x):
l, r = 0, len(nums)
while l < r:
m = l+(r-l) // 2
if nums[m] < x: #这里严格小于缩小范围会得到下边界，同理严格大于缩小范围的思路会得到上边界。很tricky的一个细节，要注意！
l = m+1
else:
r = m
return l
l = search(target)
r = search(target+1)-1
if l <= r:
return [l, r]
return [-1, -1]
'''
[5,7,7,7,7,8,8,8,10] target=8
l=search(8)
r=search(9)-1
search(x)
l=0,5,
r=9,9,
m=4,7,
nums[m]=7<8
nums[m]=8
expect output[5,7]
'''
debug: IndentationError: unexpected indent 缩进不对
时间复杂度：O（logn）
空间复杂度：O（1）
第三题 35.搜索插入位置
题目链接：https://leetcode.com/problems/search-insert-position/
难度：easy
思路：
sorted array+target需要缩小范围搜索，用二分查找
找下边界的题，都是一个套路模版，和34题几乎一样
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l=0
r=len(nums)
while l<r:
m=l+(r-l)//2
if nums[m]<target:
l=m+1else:
r=m
return l
时间复杂度：O（logn）
空间复杂度：O（1）
第四题 27.移除元素
题目链接：
https://leetcode.com/problems/remove-element/
难度：easy
思路：
要求对等于val的值被替换成其他的，剩下的不管。那就只用遍历一遍，等于va的都跳过，不等于的值才可以按顺序被替换进array，剩下的位置都是空
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
p=0
for i in range(len(nums)):
if nums[i]==val:
continue
nums[p]=nums[i]
p+=1
return p
时间复杂度：O（n）
空间复杂度：O（1）
总结：
今天刷了4道题，704，34，35都是BS，27很简单 算不上two pointers.
熟练掌握了二分查找寻找下边界的模版
学习时长2小时，效果还不错，再接再厉。
标签：二分,27,target,nums,int,复杂度,随想录,查找,移除 From： https://www.cnblogs.com/cassiehao/p/16907815.html