《剑指Offer》——数组（Python3 实现）
目录
数组
1、二维数组中的查找
问题：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路一：
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
if array==[[]]: #不能用not array，因为[[]]不为空，它是有一个元素为列表，但列表为空的数组
return False
x=len(array[0])-1
y=len(array)-1
#从左下角开始遍历
startX=0
startY=y
#循环条件，到右上点结束，因为查找方向为向右或向上
while startX<=x and startY>=0:
if array[startX][startY]>target:
startY-=1
elif array[startX][startY]<target:
startX+=1
else:
return True
return False 思路二：
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
rows=len(array)
cols=len(array[0])
for i in range(rows):
for j in range(cols):
if target==array[i][j]:
return True
return False
if __name__=='__main__':
answer=Solution()
arr=[[1,2,3],[7,8,9],[11,12,13]]
tar=9
print(answer.Find(tar,arr)) 2、旋转数组的最小数字
问题：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：最小值正好位于两段中间，用二分查找（折半查找法）即可。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
start=0
end=len(rotateArray)-1
while start<end:
mid=(start+end)//2
#中间值<最左边值，由于本身是有两个递增数组组成，所以中间值右边的不需要考虑
if rotateArray[mid]<rotateArray[start]:
end=mid
elif rotateArray[mid]>rotateArray[start]:
start=mid
else:
return rotateArray[mid+1] 3、调整数组顺序使奇数位于偶数前面
问题：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self,array):
if not array:
return []
odd=[]
even=[]
for i in array:
if i%2==1:
odd.append(i)
else:
even.append(i)
return odd+even 4、数组中出现次数超过一半的数字
问题：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
lenth=len(numbers)
a=set(numbers)
for i in a:
if numbers.count(i)>lenth/2:
return i
return 0 5、连续子数组的最大和
问题：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路：
# -*- coding:utf-8 -*-
class Solution:
def FindGreatestSumOfSubArray(self,array):
if not array:
return []
sum_arr=0
max_sum=array[0]
for i in array:
if sum_arr>0:
sum_arr+=i
else:
sum_arr=i
max_sum=max(sum_arr,max_sum)
return max_sum
if __name__=='__main__':
array=[1,-2,3,10,-4,7,2,-5]
result=Solution()
print(result.FindGreatestSumOfSubArray(array)) 6、把数组排成最小的数
问题：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
# -*- coding:utf-8 -*-
class Solution:
def cmp(self,x,y): #比较左+右，右+左，判断哪个小，然后返回
s1=str(x)+str(y)
s2=str(y)+str(x)
if s1<=s2:
return s1
if s1>s2:
return s2
def PrintMinNumber(self,numbers):
if not numbers:
return ''
numbers.sort() #由小到大排序
#不断替换index为0，1的值为cmp的返回值，直至最后数组中仅剩一个元素
while len(numbers)>1:
numbers[0]=self.cmp(numbers[0],numbers[1])
numbers.remove(numbers[1])
return numbers[0]
if __name__=='__main__':
array=[3,32,321]
result=Solution()
print(result.PrintMinNumber(array))
变形：把数组排成最大的数。
class Solution:
def cmp(self,x,y): #比较左+右，右+左，判断哪个大，然后返回
s1=str(x)+str(y)
s2=str(y)+str(x)
if s1<=s2:
return s2
if s1>s2:
return s1
def PrintMinNumber(self,numbers):
if not numbers:
return ''
numbers.sort(reverse=True) #由大到小排序
#不断替换index为0，1的值为cmp的返回值，直至最后数组中仅剩一个元素
while len(numbers)>1:
numbers[0]=self.cmp(numbers[0],numbers[1])
numbers.remove(numbers[1])
return numbers[0]
7、数字在排序数组中出现的次数
问题：统计一个数字在排序数组中出现的次数。
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
count=0
if not data or k not in data:
return 0
for i in data:
if i==k:
count+=1
return count 8、数组中只出现一次的数字
问题：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
number=[]
for i in array:
if i in number:
number.remove(i)
else:
number.append(i)
return number 9、数组中重复的数字
问题：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if numbers==None or numbers==[]:
return False
data=[]
for i in numbers:
if i in data:
duplication[0]=i
return True
else:
data.append(i)
return False 10、构建乘积数组
问题：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
思路一：下三角用连乘可以求得，上三角，从下向上也是连乘。先算下三角中的连乘，即先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
if not A:
return []
#计算左三角
num=len(A)
B=[None]*num
B[0]=1
for i in range(1,num):
B[i]=B[i-1]*A[i-1]
#计算右三角，自下而上
#保留上次的计算结果乘本轮新的数，因为只是后半部分进行累加，所以设置一个temp，能够保留上次的结果
temp=1
for i in range(num-2,-1,-1): #从后往前遍历，不算最后一个（num-1），第一个for循环已经计算了
temp*=A[i+1]
B[i]*=temp
return B 思路二：两层for循环，进行连乘，中间判断一下i != j即可。
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
n=len(A)
B=[1]*n
for i in range(n):
for j in range(n):
if i!=j:
B[i]*=A[j]
return B
查看3道真题和解析