通过定义上下左右四个边界(top、bottom、left、right),每次按顺序遍历一圈:先左→右,再上↓下,然后右→左,最后下↑上,遍历后收缩边界,直到所有元素被访问,避免使用额外空间,逻辑清晰高效。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); if (matrix == null || matrix.length == 0) return res;
int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) { for (int col = left; col <= right; col++) { res.add(matrix[top][col]); } top++;
for (int row = top; row <= bottom; row++) { res.add(matrix[row][right]); } right--;
if (top <= bottom) { for (int col = right; col >= left; col--) { res.add(matrix[bottom][col]); } bottom--; }
if (left <= right) { for (int row = bottom; row >= top; row--) { res.add(matrix[row][left]); } left++; } }
return res; } }
|
✅ 方法:先转置,再翻转
步骤 1:矩阵转置(Transpose)
- 将行列互换,即
matrix[i][j] ↔ matrix[j][i]
(只交换对角线上的上三角部分)
步骤 2:水平翻转(Horizontal Reverse)
- 每一行进行左右翻转,即
matrix[i][j] ↔ matrix[i][n - 1 - j]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } }
for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[i][n - j - 1]; matrix[i][n - j - 1] = tmp; } } } }
|
“从右上角开始查找,逐行逐列缩小搜索区域。”
为啥选右上角?
- 如果
matrix[row][col] == target
,找到了,返回 true
- 如果
matrix[row][col] > target
,说明当前列不可能包含目标值,往左移一列
- 如果
matrix[row][col] < target
,说明当前行不可能包含目标值,往下移一行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) { int val = matrix[row][col]; if (val == target) { return true; } else if (val > target) { col--; } else { row++; } }
return false; } }
|
我使用归并排序来排序链表。通过快慢指针将链表分成两半,递归地分别排序后,再合并两个有序链表。合并过程每次都以线性方式完成,总时间复杂度是 O(n log n),空间是 O(log n) 用于递归调用栈,非常适合链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head, fast = head, prev = null; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null;
ListNode l1 = sortList(head); ListNode l2 = sortList(slow);
return merge(l1, l2); }
private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = (l1 != null) ? l1 : l2; return dummy.next; } }
|
直接用最小堆一把梭
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; }
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) { if (node != null) { queue.offer(node); } } ListNode dummy = new ListNode(0); ListNode tail = dummy;
while (!queue.isEmpty()) { ListNode top = queue.poll(); tail.next = top; tail = tail.next; if (top.next != null) { queue.offer(top.next); } }
return dummy.next; } }
|
我们用两次二分查找:
- 找
target
的左边界(第一个出现的位置)
- 找
target
的右边界(最后一个出现的位置)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public int[] searchRange(int[] nums, int target) { int left = binarySearch(nums, target, true); int right = binarySearch(nums, target, false) - 1;
if (left <= right && left < nums.length && nums[left] == target && nums[right] == target) { return new int[]{left, right}; }
return new int[]{-1, -1}; }
private int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length - 1;
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } }
return -1; } }
|
遍历 nums[mid]
:
- 如果
nums[mid] == 0
:
- 把它和
nums[low]
交换,low++
,mid++
- 如果
nums[mid] == 1
:
- 如果
nums[mid] == 2
:
- 把它和
nums[high]
交换,high--
,但mid 不动(因为换过来的还没处理)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { swap(nums, low, mid); low++; mid++; } else if (nums[mid] == 1) { mid++; } else { swap(nums, mid, high); high--; } } }
private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }
|
✅ 主要分三步:
从后往前找到第一个降序位置,记为 i
:
如果找不到,说明是最大的排列,直接整体反转即可。
再从后往前找到一个比 nums[i] 大的最小的数,记为 j
,然后 交换 i 和 j。
最后反转 i+1 到数组末尾的所有元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }
if (i >= 0) { int j = nums.length - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums, i, j); }
reverse(nums, i + 1); }
private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
private void reverse(int[] nums, int start) { int end = nums.length - 1; while (start < end) { swap(nums, start, end); start++; end--; } } }
|
中位数的特性是:一半数比它小,一半数比它大。
我们可以维护两个堆:
- 大顶堆(maxHeap):存较小一半的数字
- 小顶堆(minHeap):存较大一半的数字
并保持以下两个条件:
maxHeap.size()
== minHeap.size()
或 maxHeap.size()
多 1
- 所有
maxHeap
中的数 ≤ 所有 minHeap
中的数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class MedianFinder { private PriorityQueue<Integer> maxHeap; private PriorityQueue<Integer> minHeap;
public MedianFinder() { maxHeap = new PriorityQueue<>((a, b) -> b - a); minHeap = new PriorityQueue<>(); }
public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (maxHeap.size() < minHeap.size()) { maxHeap.offer(minHeap.poll()); } }
public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.peek() + minHeap.peek()) / 2.0; } else { return maxHeap.peek(); } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); }
int m = nums1.length; int n = nums2.length; int left = 0, right = m;
while (left <= right) { int i = left + (right - left) / 2; int j = (m + n + 1) / 2 - i;
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) { if ((m + n) % 2 == 0) { return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0; } else { return Math.max(nums1LeftMax, nums2LeftMax); } } else if (nums1LeftMax > nums2RightMin) { right = i - 1; } else { left = i + 1; } } return 0; } }
|