通过定义上下左右四个边界（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;
}
}
|
