概要：此类题目的特点是会遇到一些杂乱无序的数组，经过排序后，会更好处理。
1051. 高度检查器
学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。
注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。
输入：heights = [1,1,4,2,1,3]
输出：3
解释：
当前数组：[1,1,4,2,1,3]
目标数组：[1,1,1,2,3,4]
在下标 2 处（从 0 开始计数）出现 4 vs 1 ，所以我们必须移动这名学生。
在下标 4 处（从 0 开始计数）出现 1 vs 3 ，所以我们必须移动这名学生。
在下标 5 处（从 0 开始计数）出现 3 vs 4 ，所以我们必须移动这名学生。
#思路：先建立一个正确的顺序，然后逐个对比检查原数组
class Solution:
def heightChecker(self, heights: List[int]) -> int:
z=0
for k,v in enumerate(sorted(heights)):
if v!=heights[k]:
z+=1
return z
977. 有序数组的平方
给定一个按非递减顺序排序的整数数组A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
输入：[-4,-1,0,3,10]输出：[0,1,9,16,100]
思路：创建一个新的数组存放平方后的元素，然后排序
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
ans=[]
for i in A:
ans.append(i**2)
return sorted(ans)
561. 数组拆分 I
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
输入: [1,4,3,2]输出: 4解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
思路：
（1）对于每一组里的两个元素，小的元素会被舍弃（不加入最终的求和运算）
（2）要使Sum((a0,b0),(a1,b1)......)最大，则被舍弃的元素应该尽可能小
（3）第一组（全数组最小值，全数组次小值），第二组（全数组第三小，第四小）...
（4）升序排序，然后求和即可
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
ans=sum(nums[::2])
return ans
1122. 数组的相对排序---上海国音智能面试题类似
给你两个数组，arr1 和 arr2：arr2 中的元素各不相同；arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
思路：
- 依次循环遍历arr2中的元素
- 依次从arr1中删除arr2中的元素
- 最后的元素用sorted排序，在组合新数组
class Solution(object):
def relativeSortArray(self, arr1, arr2):
res = []
for i in arr2:
while i in arr1: #这里的while仔细品
res.append(i)
arr1.remove(i) #list.remove(object) 用于移除列表中某个值的第一个匹配项
return res + sorted(arr1)
1200. 最小绝对差 ---光之树科技面试题类似
给你个整数数组 arr，其中每个元素都 不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
思路：如果A,B,C是一个排序后的数组，则排序后，C-A一定是大于B-A和C-B的
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
if not arr:
return []
#列表排序
arr.sort()
res=[]
#tmp:当前最小差值
tmp=arr[1]-arr[0]
for i in range(1,len(arr)):
#出现更小差值后，更新结果
if arr[i]-arr[i-1]<tmp:
tmp=arr[i]-arr[i-1]
res=[[arr[i-1],arr[i]]] #括号易出错,子数组也要升序排
#加入相同差值的数组
elif arr[i]-arr[i-1]==tmp:
res.append([arr[i-1],arr[i]])
else:
continue
return res
leetcode1086: 前五科的均分
给你一个不同学生的分数列表，请按照学生的id顺序返回每个学生最高的五科成绩的平均分。对于每条item[i]，item[i][0]为学生id， item[i][1]为学生的分数，平均分请采用整数除法计算。
input: [[1,91],[1,92],[2,93]...........]
output: [[1,87],[2,88]]
思路：
- 信息重点，每个学生可能不止五科，但算平均分时要计算最高的五科。
- 先用集合set找出来有多少个学生，将其id保存为id_list
- 然后按照学生的id去遍历item，找出每个学生的所有成绩。
-
排序每个学生的成绩，然后取最高的五门计算平均分。
- 将结果保存进一个新的列表里
def highFive(self,items):
id_list=list(set([i for i,j in items]))
res=[]
for id_1 in id_list:
score_arr=[]
for ids,scores in items:
if ids==id_1:
score_arr.append(scores)
sums=sum(sorted(score_arr[:5]))
res.append[id_1,int(sums/5)]
return res
581. 最短无序连续子数组
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
思路：
- 先对数组nums进行排序
- 利用两个指针，从首尾遍历，寻找排序前和排序后不一样的元素，其索引即为要找的最短子数组
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
sorted_nums=sorted(nums)
p1,p2=0,len(nums)-1
while p1<=p2 and nums[p1]==sorted_nums[p1]:
p1+=1
while p1<=p2 and nums[p2]==sorted_nums[p2]:
p2-=1
return p2-p1+1
268. 缺失数字
给定一个包含0, 1, 2, ..., n 中 n 个数的序列，找出 0 ..n 中没有出现在序列中的那个数。
思路：
- 先考虑特殊情况：首位不是0，那么缺少0，末尾不是n，那么缺少n
- else: 整个数组应该遵循 nums[i-1]+1=nums[i]，如果nums[i-1]+1！=nums[i]，那么缺少的就是nums[i-1]+1
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
if nums[-1]!=len(nums):
return len(nums)
elif nums[0]!=0:
return 0
for i in range(1,len(nums)): #从1开始检查，把0作为nums[i-1]+1的起点
expected_num=nums[i-1]+1
if nums[i]!=expected_num:
return expected_num
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
输入: [1,2], [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
思路：
- 贪心算法，优先满足胃口小的
- 先对胃口g，饼干尺寸s进行升序排序
- 让两个指针分别指向g和s的初始位置
- if 胃口g[i]<=饼干s[j]，则这块饼干j可以分给孩子i，指针i，j各移动一下，结果计数+1
- else: 无法满足胃口，将j+1，看一块更大的饼干是否满足孩子i的胃口。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
res,g_len,s_len=0,len(g),len(s)
s.sort()
g.sort()
i,j=0,0
while i<g_len and j<s_len :
if g[i]<=s[j]:
res+=1
i+=1
j+=1
else:
j+=1
return res
628. 三个数的最大乘积
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
输入: [1,2,3]
输出: 6
输入: [1,2,3,4]
输出: 24
注意:
给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
思路： 最大三个数的两种情形
- 两个负数一个正数
- 三个正数
- 先对数组排序，要么排序后末尾三个为正数，要么前面两负一正，只有这两种可能
class Solution:
def maximumProduct(self,nums):
nums.sort()
v1=nums[-1]*nums[-2]*nums[-3]
v2=nums[0]*nums[1]*nums[-1]
return max(v1,v2)
976. 三角形的最大周长
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
输入：[2,1,2]
输出：5
输入：[1,2,1]
输出：0
输入：[3,2,3,4]
输出：10
思路：三角形充分必要条件：a+b>c，假设已经知道c的长度了，只需要尽可能选大的a和b
class Solution:
def largestPerimeter(self, A: List[int]) -> int:
A.sort()
for i in range(len(A)-3,-1,-1):
if A[i]+A[i+1]>A[i+2]:
return A[i]+A[i+1]+A[i+2]
return 0
