一、如何找出数组中丢失的数
题目描述：给定一个由n-1个整数组成的未排序的数组序列，其原始都是1到n中的不同的整数，请写出一个寻找数组序列中缺失整数的线性时间算法
方法1：累加求和 时间复杂度是O(N)
方法2：异或法,要先对实际无缺失的arr中的值异或，然后再对估计的值异或;缺失的值就是最终异或得到的值 时间复杂度O(N)
方法3：遍历一遍，用字典记录数字出现的次数，遇到出现2次的就返回
方法1、2代码
from functools import reduce
class Solution:
def getNum1(self,arr):#累加求和
real_list = [i for i in range(1,len(arr)+2)]
real_sum = reduce(lambda x,y:x+y,real_list)
estimate_sum = sum(arr)
return real_sum-estimate_sum
def getNum2(self,arr):
real_list = [i for i in range (1, len (arr) + 2)]
real_ = reduce(lambda x,y:x^y,real_list)
estimate_ = reduce(lambda x,y:x^y,arr)
return real_^estimate_
S = Solution()
res = S.getNum2(arr=[1,4,3,2,7,5])
print(res)
二、如何找出旋转数组中的最小元素
题目描述：将一个有序数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3,4,5,1,2]为数组[1,2,3,4,5]的一个旋转，该数组的最小值为1
方法1：遍历该数组的所有元素，选出最小的元素
方法2：二分查找
【1】如果中间值比右边值大，说明最小值在右侧
【2】如果中间值比右边值小，说明最小值在左侧
【3】如果中间值比前一个值大， 那中间值一定是最小值
【4】如果中间值比后一个值大，那后一个值一定是最小值
【5】如果中间值等于low值，且中间值等于high值，则无法判断最小值在哪，需要求出两边分别的最小值，再比较
分析：二分查找时间复杂度是O(log2N)，最坏情况O(N)[第五种情况]
难点在于要考虑2种情况：
【1】数组中元素只全部相等，如[1,1,1,1]
【2】数组中元素只大部分都相等，如[1,0,1,1,1,1]
方法2代码如下：
def getMin1(arr,low,high):
if high < low:
return arr[0]
if high == low:#只剩下一个元素一定是最小值
return arr[low]
mid = (low+high) // 2
if arr[mid] < arr[mid-1]:#45123，1一定是最小值【奇数】
return arr[mid]
elif arr[mid+1] < arr[mid]: #456123,1一定是最小值【偶数】
return arr[mid+1]
elif arr[mid] > arr[high]:#最小值在右侧
low = mid + 1
return getMin1(arr,low,high)
elif arr[mid] < arr[high]:#最小值在左侧
high = mid
return getMin1(arr,low,high)
else:#这种情况无法确定最小值所在的位置，需要左右两部分分别查找
return min(getMin1(arr,low,mid-1),getMin1(arr,mid+1,high))
def getMin(arr):
if not arr:
return
else:
return getMin1(arr,0,len(arr)-1)
引申：如何实现旋转数组功能？
思路：先分别对两个子数组内部进行交换，然后再对两个数组进行交换
举例：x1=[1,2,3],x2=[4,5,6]--->x1'=[3,2,1],x2'=[6,5,4]
--->x'=[3,2,1,6,5,4]
--->x=[4,5,6,1,2,3] 最终结果
#方法一：空间复杂度O(N)
def rotateArr(arr,div):
'''
:param arr:
:param div:分为两个数组的切割点
:return:
'''
arr1 = arr[:div+1]
arr2 = arr[div+1:]
return arr2+arr1
#方法二：时间复杂度O(N),空间复杂度O(1)
def rotateArr1(arr,div):
def swap(arr,low,high):
while low < high:
arr[low],arr[high] = arr[high],arr[low]
low += 1
high -= 1
if not arr or div < 0 or div >= len(arr):
return
# if div == 0 or div == len(arr) - 1:
# return
swap(arr,0,div)#交换第一个子数组
print(arr)
swap(arr,div+1,len(arr)-1)#交换第二个子数组
print(arr)
swap(arr,0,len(arr)-1)#交换整个数组
print(arr)
return arr
三、找数组中的最大值和最小值
题目描述：给定数组，找出最大值和最小值，假设值两两不相同
方法1: 遍历一遍，记录最大最小值
最差情况，要比较2n-2次;最好情况，比较n-1次
时间复杂度：O(n)
方法2: 分治法,两两分组,对组中的两个元素排序,找最大值就找组内第二个元素,找最小值就找组内第一个元素;最后一个元素要特殊考虑一下
比较次数n/2,找最大最小值比较2*(n/2-1)次,总比较次数 3n/2-2次
时间复杂度:O(n)
方法3：递归实现分治法
思路：将数组分成两部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后综合起来，左右两部分的最大(小)值中的较大值即为合并后的数组的最大(小)值，直到划分区间内只剩一个元素或者两个元素为止
方法2代码如下：
class MaxMin:
def __init__(self):
self.max = None
self.min = None
def getMax(self):
return self.max
def getMin(self):
return self.min
def GetMaxandMin(self,arr):
if arr == None:
print('参数不合法')
return
i = 0
lens = len(arr)
self.max = arr[0]
self.min = arr[0]
#两两分组，把较小的数放到左半部分，较大的数放到右半部分
while i < lens-1:
if arr[i] > arr[i+1]:
arr[i],arr[i+1] = arr[i+1],arr[i]
i += 2
print(arr)
#比较每组的左半部分，找最小值
self.min = arr[0]
i = 2
while i < lens:
if arr[i] < self.min:
self.min = arr[i]
i += 2
#比较每组的右半部分，找最大值
self.max = arr[1]
i = 3
while i < lens:
if arr[i] > self.max:
self.max = arr[i]
i += 2
#如果数组中元素个数是奇数个，最后一个元素被分为一组，需要特殊处理
if lens % 2 == 1:
if self.max < arr[lens-1]:
self.max = arr[lens-1]
if self.min > arr[lens-1]:
self.min = arr[lens-1]
print(self.max)
print(self.min)
方法3代码：
class MaxMin_recur:
def __init__(self):
self.max = None
self.min = None
def getMax(self):
return self.max
def getMin(self):
return self.min
def GetMaxandMin(self,arr,l,r):
if arr == None:
return
mid = (l + r) // 2
list = []
#如果只有一个元素
if l == r:
list.append(arr[l])
list.append(arr[l])
return list
#如果有两个元素
if l + 1 == r:
if arr[l] >= arr[r]:
max_ = arr[l]
min_ = arr[r]
else:
max_ = arr[r]
min_ = arr[l]
list.append(min_)
list.append(max_)
return list
L_list = self.GetMaxandMin(arr,l,mid)
R_list = self.GetMaxandMin(arr,mid+1,r)
#总的最大值
max_ = L_list[1] if (L_list[1] > R_list[1]) else R_list[1]
min_ = L_list[0] if (L_list[0] < R_list[0]) else R_list[0]
list.append(min_)
list.append(max_)
return list
if __name__ == '__main__':
maxmin = MaxMin_recur()
arr = [1,3,6,5,14]
l = 0
r = len(arr) - 1
result = maxmin.GetMaxandMin(arr,l,r)
print(result)
四、如何找出数组中出现奇数次的数
题目描述：1.数组中有N+2个数，其中，N个数出现了偶数次，2个数出现了奇数次（这2个数不相等）
2.数组中有N+3个数，其中，N个数出现了偶数次，3个数出现了奇数次（这3个数不相等）
3.数组中有一个数出现1次，其他数都出现2次，找出该数
4.数组中有一个数出现1次，其他数都出现3次，找出该数
5.数组中有一个数出现1次，其他数都出现N次，找出该数
6.数组中除了三个数出现1次，其他数都出现偶数次。找出这些数
说明：请用O(1)的空间复杂度，找出这两个数。注意:不需要知道具体位置，只需要找出这两个数
1. 2个数出现了奇数次
方法1：用dict记录，每个元素的次数，最后返回，出现次数为2的元素
方法2：用异或，首先对所有的元素异或，得到那两个奇数的异或，如果该结果不为0，就说明这两个出现一次的数至少有一位是不一样的，我们就可以将原先的数组该位为1或0的数分为两组，然后再对两组分别进行异或，就能分别得到两个数，这两个数就是出现一次的数
方法1代码：
class Solution:
def getNum_1(self,arr):
arr_dict = {}
for num in arr:
if num not in arr_dict:#出现一次
arr_dict[num] = 1
else:#出现两次
arr_dict[num] = 0
res = [k for k,v in arr_dict.items() if v == 1]#出现一次的元素value必定为1
return res
方法2代码：
class Solution:
def getNum_3(self, arr):
if not arr or len(arr) < 1:
return
result1 = 0
pos = 0
i = 0
while i < len(arr):
result1 = result1^arr[i]
i += 1
tmpResult = result1
print('tmpResult',tmpResult)
i = result1
while i&1 == 0:#从二进制右往左，找到第一个1所在的位
print(i,1,i&1)
pos += 1
i = i>>1
print('pos',pos)
i = 1
while i<len(arr):
if ((arr[i]>>pos)&1) == 1:#异或的结果与所有第position位为1的数异或,结果一定是出现一次的两个数中其中一个
result1 = result1^arr[i]
i += 1
result2 = result1^tmpResult
return result1,result2
2. 3个数出现了奇数次，求3个数中的一个
思路:先对所有数字进行异或,重复数异或得0,这样就能得到三个数异或的结果，因为三个数字只出现过一次，显然这三个数字不相同，因此，这三个数对应的二进制数也不可能完全相同。这样取某位为1的数，就能将三个数分为两组，一组包含三个数中的两个数，另外一组包含三个数中的一个数。统计两组元素的个数，如果一组数的个数为偶数，就说明有三个数中的两个数在这组内，再将这组元素进行异或，取某位为1分为两组，两组分别异或就能分别得到两个数;另一个数,将其组内元素异或就能得到第三个数。
代码如下:
#判断数字n的二进制数从右往左数第i位是否为1
'''
思路：1<<i可以表示从右向左第i位为1，其余位为0的指示数
用n与有特定位的指示数与或，就能判断n的特定位是否为1,【长数和短数与或只比较到短数的长度】
'''
def isOne(n,i):
# print(n,1<<i)
return (n&(1<<i))!=0
# res = isOne(10,1)
# print(res)
from functools import reduce
def findSingle(arr):
all_yihuo = reduce(lambda x,y:x^y,arr)
print('all_yihuo',all_yihuo)
pos1 = 0
for wei in range(len(arr),-1,-1):
if isOne(all_yihuo,wei) == True:#找从右向左异或为1的位
pos1 = wei
break
#按照pos1这个位为1，将原数组一分为2
arr1 = []
arr0 = []
for num in arr:
if num&(1<<pos1) > 0:
arr1.append(num)
else:
arr0.append(num)
print(arr1)
print(arr0)
print('pos1',pos1)
res = 0
if len(arr1) % 2 == 1:
res = reduce(lambda x,y:x^y,arr1)
else:
res = reduce(lambda x,y:x^y,arr0)
return res
3.数组中有一个数出现1次，其他数都出现2次，找出该数
思路：对数组中所有数异或，最后的值就是所求的值，因为出现两次的值，异或之后为0。
4.数组中有一个数出现1次，其他数都出现3次，找出该数
python自带count功能
代码如下：
# 示例 1: # 输入: [2,2,3,2] # 输出: 3 # 示例 2: # 输入: [0,1,0,1,0,1,99] # 输出: 99 def singleNumber(nums): for i in nums: if nums.count(i) == 1: return i nums = [0,1,0,1,0,1,99] res = singleNumber(nums) print(res)
5.数组中有一个数出现1次，其他数都出现N次，找出该数
思路同上
6.数组中除了三个数是出现1次，其余的数都出现偶数次，找出三个数中的任意一个
思路：对所有数字进行异或,重复数异或得0,这样就能得到三个数异或的结果，因为三个数字只出现过一次，显然这三个数字不相同，因此，这三个数对应的二进制数也不可能完全相同。
这样取某位为1的数，就能将三个数分为两组，一组包含三个数中的两个数，另外一组包含三个数中的一个数
统计两组元素的个数，如果一组数的个数为偶数，就说明有三个数中的两个数在这组内，再将这组元素进行异或，取某位为1分为两组，两组分别异或就能分别得到两个数;另一个数,将其组内元素异或就能得到第三个数
小tips：判断数字n的二进制数从右往左数第i位是否为1 ==>> (n&(1<<i))!=0
例子：n=9，二进制为1001，要判断n的第三位是否为1，就可以用1001&(1<<3)=0，表明n的第三位不是1
代码如下：
判断数字n的二进制数从右往左数第i位是否为1 ''' 思路：1<<i可以表示从右向左第i位为1，其余位为0的指示数 用n与有特定位的指示数与或，就能判断n的特定位是否为1,【长数和短数与或只比较到短数的长度】 ''' def isOne(n,i): # print(n,1<<i) return (n&(1<<i))!=0 # res = isOne(10,1) # print(res) from functools import reduce def findSingle(arr): all_yihuo = reduce(lambda x,y:x^y,arr) print('all_yihuo',all_yihuo) pos1 = 0 for wei in range(len(arr),-1,-1): if isOne(all_yihuo,wei) == True:#找从右向左异或为1的位 pos1 = wei break #按照pos1这个位为1，将原数组一分为2 arr1 = [] arr0 = [] for num in arr: if num&(1<<pos1) > 0: arr1.append(num) else: arr0.append(num) print(arr1) print(arr0) print('pos1',pos1) res = 0 if len(arr1) % 2 == 1: res = reduce(lambda x,y:x^y,arr1) else: res = reduce(lambda x,y:x^y,arr0) return res res = findSingle([1,2,4,5,6,4,2]) print(res)
五、找出数组中第k小的数
题目描述：给定一个整数数组，如何快速地求出该数组中第k小的数。假如数组为[4,0,1,0,2,3],那么第3小的元素是1
方法1:整体排序 (最高效的排序算法【快排】的平均时间复杂度是O(Nlog2N)，因此，该方法的平均时间复杂度为O(Nlog1N))
方法2:部分排序法，选择排序，第一次遍历从数组中找出最小的数，第二次遍历从剩下的数中找出最小的数(在整个数组中是第二小的数)，第k次遍历就可以从N-K+1个数中找出最小的数，时间复杂度是O(N*k);也可以用堆排序进行k趟排序找出第k小的值
方法3:类快速排序方法
[1]如果i-low==k-1,说明array[i]就是第k小的元素，那么直接返回array[i]
[2]如果i-low>k-1,说明第k小的元素肯定在array[low...i-1]中,那么只需要递归地在array[low...i-1]中找第k小的元素即可
[3]如果i-low<k-1,说明第k小的元素肯定在array[i+1...high]中，那么只需要递归地在arra[i+1...high]中找第k-(i-low)-1小的元素即可
方法1、3代码：
class Solution:
def findSmallK_1(self,array,k):
array = sorted(array)
return array[k]
def findSmallK_2(self,array,low,high,k):
i = low
j = high
splitElem = array[i]
'''把小于等于splitElem的数放到数组中splitElem的左边，大于splitElem的值放到右边'''
while i < j:
while i < j and array[j] >= splitElem:#从后往前找到第一个小于splitElem的数停止
j -= 1
if i < j:
array[i] = array[j]
i += 1
while i < j and array[i] <= splitElem:#从前往后找到第一个大于splitElem的数停止
i += 1
if i < j:
array[j] = array[i]
j -= 1
array[i] = splitElem
subArrayIndex = i-low
if subArrayIndex == k-1:
return array[i]
elif subArrayIndex > k-1:
return self.findSmallK_2(array,low,i-1,k)
else:
return self.findSmallK_2(array,i+1,high,k-(i-low)-1)
S = Solution()
array=[4,0,5,0,2,3]
low=0
high=len(array)-1
k=3
res = S.findSmallK_2(array,low,high,k)
print(res)
六、找出数组中前k大的数（O(N)）
题目描述:O(N)时间复杂度内查找数组中前三名
思路1：对整个数组进行排序，然后根据数组下标找出最大的三个数，但是这种方法最好的时间复杂度是O(Nlog2N)
思路2：采用类似求最大值的方法来求前三名，初始化前三名，然后遍历数组
[1]如果当前值tmp大于r1: r3=r2,r2=r1,r1=tmp;
[2]如果当前值tmp大于r2且不等于r1: r3=r2,r2=tmp
[3]如果当前值tmp大于r3且不等于r2: r3=tmp
方法2代码：
def findTop3(arr):
if not arr or len(arr) < 3:
return
r1 = r2 = r3 = -2**31
i = 0
while i <len(arr):
if arr[i] > r1:
r3 = r2
r2 = r1
r1 = arr[i]
elif arr[i] > r2 and arr[i] != r1:
r3 = r2
r2 = arr[i]
elif arr[i] > r3 and arr[i] != r2:
r3 = arr[i]
i += 1
print(r1,r2,r3)
arr = [4,5,1,2,3,4,7,8,12]
findTop3(arr)