Leetcode数组题目
学习一时爽，一直学习一直爽
本文来自数据结构与算法之美 春节加餐
争哥：https://github.com/wangzheng0822/algo
数组题目
在这里插入图片描述
这不补下春节欠的债
Three Sum（求三数之和）
leetcode的第15题
https://leetcode-cn.com/problems/3sum/
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
对于twosum就是遍历寻找另一个是不是在nums中
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
'''
1、首先我们需要排序
2、循环nums
3、固定一个值，找另外二个值它们和等于 0
4、如果三个数相加等于零则存储到相应的二维数组中
:param nums:
:return:
'''
result = []
nums.sort()
a = len(nums)
# 固定最后值 找前面另外二个值它们和等于 0
for i in range(a - 1):
# 遍历前面的数组 如果它们和等于 0
for j in range(i + 1, a):
if -(nums[i] + nums[j]) in nums[j + 1:]:
array = [nums[i], nums[j], -(nums[i] + nums[j])]
if array not in result:
result.append(array)
return result但是这超时了,o(n2)时间复杂度不行
在这里插入图片描述 这是就有一种很特别的方法，
作者：jyd 链接：https://leetcode-cn.com/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/ 来源：力扣（LeetCode）
解题思路：
- 暴力法搜索为 O(N^3)O(N 3 )
时间复杂度，可通过双指针动态消去无效解来优化效率。
- 双指针法铺垫：先将给定 nums 排序，复杂度为 O(NlogN)O(NlogN)。
双指针法思路：固定 3 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：
当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 33 个数字都大于 00 ，在此固定指针 k 之后不可能再找到结果了。
当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
- 当s < 0时，i += 1并跳过所有重复的nums[i]；
- 当s > 0时，j -= 1并跳过所有重复的nums[j]；
- 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。
class Solution:
def threeSum(self, nums):
# 如果列表长度小于3，则条件不成立，返回空列表
if len(nums) < 3: return []
n = len(nums)
# 先排序
nums.sort()
list_nums = []
# 从列表第一个数开始循环，和它右边选两个数相加，求和
# 所以只能到倒数第三个数为止，因为倒数第二个数右边只有一个数
for i in range(n - 2):
# 因为列表已经按从小到大顺序排列了，如果左边数字大于0，则右边一定大于0
# 则三数之和不可能为0
if nums[i] > 0:
break
# 从第一个元素开始，如果它的左边元素和它相等，则跳过进行下一轮循环
if i >= 1 and nums[i - 1] == nums[i]:
continue
# 分别从当前元素右边第一个元素和最右边元素开始，计算三个元素之和
left, right = i + 1, n - 1
# 如果左路元素没有和右路元素相交，则继续靠近
while left < right:
sums = nums[i] + nums[left] + nums[right]
if sums == 0:
list_nums.append([nums[i], nums[left], nums[right]])
# 从左边开始移动到最后一个重复元素
while left < right and nums[left] == nums[left + 1]:
left += 1
# 从右边开始移动到最后一个重复元素
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 跳过重复元素
left, right = left + 1, right - 1
elif sums < 0:
left += 1
else:
right -= 1
return list_nums将python改写成Java，思路一样
class Solution {
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<List<Integer>>();
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int left = i+1, right = num.length-1, sum = 0 - num[i];
while (left < right) {
if (num[left] + num[right] == sum) {
res.add(Arrays.asList(num[i], num[left], num[right]));
while (left < right && num[left] == num[left+1]) left++;
while (left < right && num[right] == num[right-1]) right--;
left++; right--;
} else if (num[left] + num[right] < sum) left++;
else right--;
}
}
}
return res;
}
}leetcode 第169题
https://leetcode-cn.com/problems/majority-element/
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
暴力算法
暴力算法遍历整个数组，然后用另一重循环统计每个数字出现的次数。将出现次数比其他数字加起来出现次数还多的元素返回。
class Solution:
def majorityElement(self, nums):
majority_count = len(nums)//2
for num in nums:
count = sum(1 for elem in nums if elem == num)
if count > majority_count:
return num但是两次遍历时间复杂度O(n2),超时了
将nums排序，那些众数一定在中间
时间复杂度：O(nlgn)O(nlgn)
用 Python 和 Java 将数组排序开销都为 O(nlgn)O(nlgn) ，它占据了运行的主要时间。
空间复杂度：O(1)O(1)或者O(n)O(n)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums)//2]但是py时间复杂度太大了
在这里插入图片描述
同样的方法用Java写
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}速度快了几百倍
在这里插入图片描述
排序法是最好的方法
https://leetcode-cn.com/problems/first-missing-positive/
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
return的一定是0到len(nums)中的一个正整数
class Solution(object):
def firstMissingPositive(self, nums):
for i in range(1,len(nums)+2):
if i not in nums:
return i改写成Java，思路一样
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
int[] arr = new int[len+2];//定义一个新数组，最小的数字肯定就在新数组的下标中
for (int item : nums) {
if (item > 0 && item <= len) {
//排除负数和大于输入数组长度的数，因为缺失的正数肯定小于数组的长度+1（这里需要仔细想清楚）
arr[item] = 1;//新数组下标为1，则表示有这个数
}
}
//这一步就简单了，遍历新数组，看看第一个没有的正整数是谁就行了
for (int i = 1; i < len+2; i++) {
if (0 == arr[i]) {
return i;
}
}
return len+1;//这一步为了应对空数组
}
}