第一题-----------------------------------------------------
给定一个无序数组,数组里都是正整数,找中位数
[思路] 方法一是快排思想,二是用堆。放一个快排的代码:
class solution():
def partition(self,nums,left,right):
key=nums[left]
while left<right:
while left<right and nums[right]>=key:
right-=1
nums[left]=nums[right]
while left<right and nums[left]<=key:
left+=1
nums[right]=nums[left]
nums[left]=key
return left
def func(self,nums):
start = 0
end= len(nums) - 1
mid=(start+end)//2
ind=self.partition(nums,start,end)
while ind!=mid:
if ind<mid:
ind=self.partition(nums,ind+1,end)
else:
ind = self.partition(nums, start,ind-1)
return nums[ind]
nums=[2,3,1,5,7,6,4]
print(solution().func(nums))
这个是经典题型了,详细的可以参考链接: blog.csdn.net/oneday_789/…
第二题-----------------------------------------------------
给定一个无序数组,数组里都是正整数,找使得奇数与偶数个数相同的最长子序列(连续的)。
【思路:】
【代码】python代码:
arr=[1,1,-1,1,1,-1,-1]
arr2=[1,-1,1,-1,1,-1,1,-1]
def func(arr):
dp=[0 for _ in range(len(arr))]
dp[0]=arr[0]
max_len=0
dic_={dp[0]:0}
left=0
right=0
for i in range(1,len(arr)):
dp[i]=dp[i-1]+arr[i]
if dp[i] not in dic_.keys():
dic_[dp[i]]=i
if max_len<i-dic_[dp[i]]:
max_len=max(max_len,i-dic_[dp[i]])
left=dic_[dp[i]]
right=i
if dp[-1]==0:
return arr
return arr[left + 1:right + 1]
print(func(arr2))
是这道题的一个变形,大家可以参考: www.cnblogs.com/coding-wtf/…