数组相关算法题
189. 旋转数组
给定一个数组，将数组中的元素向右移动
k个位置，其中k是非负数。>输入: nums = [1,2,3,4,5,6,7], k = 3 >输出: [5,6,7,1,2,3,4] >解释: >向右旋转 1 步: [7,1,2,3,4,5,6] >向右旋转 2 步: [6,7,1,2,3,4,5] >向右旋转 3 步: [5,6,7,1,2,3,4]>输入：nums = [-1,-100,3,99], k = 2 >输出：[3,99,-1,-100] >解释: >向右旋转 1 步: [99,-1,-100,3] >向右旋转 2 步: [3,99,-1,-100]
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0)
return;
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
public void reverse(int[] nums, int l, int r) {
while (l < r){
int t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}
}1. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
>输入：nums = [4,5,6,7,0,1,2], target = 0 >输出：4>输入：nums = [4,5,6,7,0,1,2], target = 3 >输出：-1>输入：nums = [1], target = 0 >输出：-1
思路：如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if(nums[mid] < nums[right]) {
// 注意边界
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
} else {
// 注意边界
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
}2. 两数之和(4897)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
>输入：nums = [2,7,11,15], target = 9 >输出：[0,1] >解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。>输入：nums = [3,2,4], target = 6 >输出：[1,2]>输入：nums = [3,3], target = 6 >输出：[0,1]
// 双指针
class Solution {
public int[] twoSum(int[] nums, int target) {
int p1 = 0, p2 = nums.length - 1;
while (p1 < p2) {
int sum = nums[p1] + nums[p2];
if (sum < target) p1++;
else if (sum > target) p2--;
else return new int[] {p1, p2};
}
return new int[]{};
}
}3. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
>输入：nums = [-1,0,1,2,-1,-4] >输出：[[-1,-1,2],[-1,0,1]]>输入：nums = [] >输出：[]>输入：nums = [0] >输出：[]
排序过后的双指针，注意重复
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序
Arrays.sort(nums);
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// 判断是否元素大于0,大于0，没必要操作了
if (nums[i] > 0)
break;
// 判断是否重复
if (i > 0 && nums[i] == nums[i - 1])
continue;
// 双指针操作
int l = i + 1, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] < -nums[i]) l++;
else if (nums[l] + nums[r] > -nums[i]) r--;
else {
// 相等了哈
ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
// 防止重复
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
return ls;
}
}5、顺时针打印矩阵
跟lc的螺旋矩阵一样
public class T19 {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
while(r1 <= r2 && c1 <= c2) {
for (int i = c1; i <= c2; i++) {
list.add(matrix[r1][i]);
}
for (int i = r1 + 1; i <= r2; i++) {
list.add(matrix[i][c2]);
}
// 注意边界
if (r1 != r2) {
for (int i = c2 - 1; i >= c1; i--) {
list.add(matrix[r2][i]);
}
}
// 注意边界
if (c1 != c2) {
for (int i = r2 - 1; i >= r1; i--) {
list.add(matrix[i][c1]);
}
}
r1++; r2--; c1++; c2--;
}
return list;
}
}6. 缺失的第一个正数
给你一个未排序的整数数组
nums，请你找出其中没有出现的最小的正整数。>输入：nums = [1,2,0] >输出：3>输入：nums = [3,4,-1,1] >输出：2>输入：nums = [7,8,9,11,12] >输出：1
采用排序的犯规操作
class Solution {
public int firstMissingPositive(int[] nums) {
int ans = 1;
// 犯规操作
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > ans) break;
if (nums[i] == ans) ans++;
}
return ans;
}
}448. 找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
>输入: >[4,3,2,7,8,2,3,1] >输出: >[5,6]
/**
* 【笔记】将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
*
* 举个例子：
*
* 原始数组：[4,3,2,7,8,2,3,1]
*
* 重置后为：[-4,-3,-2,-7,8,2,-3,-1]
*
* 结论：[8,2] 分别对应的index为[5,6]（消失的数字）
*/
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (Integer num : nums) {
nums[Math.abs(num) - 1] = -Math.abs(nums[Math.abs(num) - 1]);
}
List<Integer> list = new ArrayList<>();
for(int i = 0; i < nums.length; i++) {
if (nums[i] > 0)
list.add(i + 1);
}
System.out.println(list.toString());
return list;
}
}560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
>输入:nums = [1,1,1], k = 2 >输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
class Solution {
/**
扫描一遍数组, 使用map记录出现同样的和的次数, 对每个i计算累计和sum并判断map内是否有sum-k
**/
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, ret = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
ret += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return ret;
}
}56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
>输入：intervals = [[1,3],[2,6],[8,10],[15,18]] >输出：[[1,6],[8,10],[15,18]] >解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].>输入：intervals = [[1,4],[4,5]] >输出：[[1,5]] >解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new ArrayList<>();
int i = 0;
int n = intervals.length;
while (i < n) {
int l = intervals[i][0];
int r = intervals[i][1];
while (i < n - 1 && r >= intervals[i + 1][0]) {
r = Math.max(r, intervals[i + 1][1]);
i++;
}
list.add(new int[] {l, r});
i++;
}
return list.toArray(new int[list.size()][2]);
}
}674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int d = 0;
int max = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1])
max = Math.max(i - d + 1, max);
else
d = i;
}
return max;
}
}986. 区间列表的交集
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
>输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] >输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]>输入：firstList = [[1,3],[5,9]], secondList = [] >输出：[]
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> list = new ArrayList<>();
for (int i = 0, j = 0; i < A.length && j < B.length;) {
int l = Math.max(A[i][0], B[j][0]);
int r = Math.min(A[i][1], B[j][1]);
if (l < r)
list.add(new int[]{l, r});
else if (l == r)
list.add(new int[] {l, l});
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return list.toArray(new int[list.size()][]);
}
}本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论