Leetcode数组题目
- 2019 年 11 月 14 日
- 笔记
学习一时爽，一直学习一直爽
本文来自数据结构与算法之美 春节加餐
争哥：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;//这一步为了应对空数组 } }
