标签： medium

目标

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，返回 target 在数组中的下标，如果不在返回 -1，要求时间复杂度为 O(log n)。

所谓的旋转可以理解为以 k 为分界点将数组分为两段，后面的放到前面，前面的放到后面。相当于两个有序数组拼在一起，且前面数组的每个元素都比后面数组的每个元素都大。

• 如果 target 在左侧，m 在右侧，直接排除右侧
• 如果 target 在右侧，m 在左侧，直接排除左侧
• 如果在同一侧直接按照正常的有序二分即可

进阶的版本是 81.搜索旋转排序数组II。

代码

/**
 * @date 2026-05-22 09:13
 */
public class Search33 {

    public int search_v3(int[] nums, int target) {
        int r = nums.length - 1, l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            // 如果 target 在左侧，m 在右侧，直接排除右侧
            if (target >= nums[0] && nums[m] < nums[0]) {
                r = m - 1;
            } else if (target < nums[0] && nums[m] >= nums[0]) {
                // 如果 target 在右侧，m 在左侧，直接排除左侧
                l = m + 1;
                // 如果在同一侧直接按照正常的有序二分即可
            } else if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return -1;
    }

}

性能

目标

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

说明：

• 1 <= arr1.length, arr2.length <= 5 * 10^4
• 1 <= arr1[i], arr2[i] <= 10^8

思路

有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。

将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。

或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。

代码

/**
 * @date 2026-05-21 9:03
 */
public class LongestCommonPrefix3043 {

    static class Trie {
        public Trie[] children = new Trie[10];

        public void insert(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    cur.children[d] = new Trie();
                }
                cur = cur.children[d];
            }
        }

        public int prefixLength(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            int l = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    break;
                }
                cur = cur.children[d];
                l++;
            }
            return l;
        }
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie root = new Trie();
        for (int num : arr1) {
            root.insert(num);
        }
        int res = 0;
        for (int num : arr2) {
            res = Math.max(res, root.prefixLength(num));
        }
        return res;
    }

}

性能

目标

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

说明：

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• 题目保证 A 和 B 两个数组都是 n 个元素的排列。

思路

有两个长度为 n 的整数排列 A 和 B，整数 1 ~ n 恰好出现一次，C[i] 表示 A[0, i] 和 B[0, i] 中的公共元素个数（注意不是公共前缀长度），返回 C。

直接依题意模拟，使用哈希表（或者数组计数），A 中元素 +1， B 中元素 -1，然后累加出现次数为 0 的元素个数即可。注意元素相同时避免重复累加，并且当前位置公共元素的个数应该以前一个位置公共元素的个数为基础再加上新增公共元素的个数。

网友题解使用的是位运算，注意到 n <= 50，可以使用两个 long 型变量来记录元素是否出现，将这两个变量相与然后 bitcount 就是公共元素个数。

代码

/**
 * @date 2026-05-20 8:58
 */
public class FindThePrefixCommonArray2657 {

    public int[] findThePrefixCommonArray_v1(int[] A, int[] B) {
        int n = A.length;
        int[] cnt = new int[n + 1];
        int[] C = new int[n];
        cnt[A[0]]++;
        cnt[B[0]]--;
        if (A[0] == B[0]) {
            C[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            cnt[A[i]]++;
            cnt[B[i]]--;
            C[i] = C[i - 1];
            if (cnt[A[i]] == 0) {
                C[i]++;
            }
            if (A[i] != B[i] && cnt[B[i]] == 0) {
                C[i]++;
            }
        }
        return C;
    }

}

性能

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

说明：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

所谓旋转，可以视为循环数组向右移动。虽然不是整体有序，但还是可以使用二分。由于元素值互不相同，根据第一个元素可以判断属于哪一部分，进而可以确定搜索方向。

如果大于第一个元素向右搜索，如果小于则向左搜索，注意如果返回的下标是 n 需要对 n 取余指向第一个元素。

代码

/**
 * @date 2024-08-31 22:37
 */
public class FindMin153 {

    public int findMin_v2(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

目标

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

说明：

• n == nums.length
• 2 <= n <= 10^5
• 1 <= nums[i] <= limit <= 10^5
• n 是偶数。

思路

有一个长度为偶数的数组 nums 和一个整数 limit，每次操作可以将任意元素替换为 [1, limit] 中的任意整数，求使得 nums 互补的最少操作次数。所谓互补指 nums[i] + nums[n - 1 - i] 的和都相等。

由于 1 <= nums[i] <= limit，每一对元素和都可以变成 [2, 2 * limit] 中的任意数字。

令 a = nums[i], b = nums[n - 1 - i], sum = a + b，如果只操作一次，考虑左侧 a -> 1 或者 b -> 1，sum 最多变化 max(a, b) - 1；右侧 a -> limit 或者 b -> limit，sum 最多变化 limit - min(a, b)。

• 将 sum 变成区间 [sum - (max(a, b) - 1), sum - 1], [sum + 1, sum + limit - min(a, b)] 内的值需要操作一次
• 变成 sum 的操作次数不变
• 其它 [2, sum - (max(a, b) - 1) - 1], [sum + limit - min(a, b) + 1, 2 * limit] 需要操作两次

使用差分数组来记录每对元素和变成目标和所需的操作次数，最后遍历所有目标和，取操作次数最小的即可。

代码

/**
 * @date 2026-05-13 10:13
 */
public class MinMoves1674 {

    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int max = 2 * limit;
        int[] diff = new int[max + 2];
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int sum = a + b;
            int l = sum - (Math.max(a, b) - 1);
            int r = sum + (limit - Math.min(a, b));
            diff[2] += 2;
            diff[Math.max(2, l)]--;
            diff[sum]--;
            diff[Math.min(sum + 1, max + 1)]++;
            diff[Math.min(r + 1, max + 1)]++;
        }
        int sum = 0, res = Integer.MAX_VALUE;
        for (int i = 2; i <= max; i++) {
            sum += diff[i];
            res = Math.min(sum, res);
        }
        return res;
    }

}

性能

目标

给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：

返回执行 k 次循环轮转操作后的矩阵。

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• m 和 n 都是 偶数
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 10^9

思路

有一个 m x n 矩阵 grid，m 与 n 都是偶数，矩阵里外分层，每次轮转用元素取代对应层逆时针方向的下一个元素，求轮转 k 次之后的矩阵。

m x n 矩阵有 Math.min(m/2, n/2) 层，最外层有 2 * (m + n) - 4 个元素，下一层用 m - 2， n - 2 代入，得到比上一层少 8 个元素，以此类推。

将每一层映射到一维进行轮转，然后再赋值回去即可。可以使用方向向量来赋值，碰到边界就转向。

参考 874.模拟行走机器人 2069.模拟行走机器人II 59.螺旋矩阵II

代码

/**
 * @date 2026-05-09 9:26
 */
public class RotateGrid1914 {

    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int layer = Math.min(m / 2, n / 2);
        int[][] arr = new int[layer][];
        int length = 2 * (m + n) - 4;
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0, x = 0, y = 0, d = 0; i < layer; i++, x++, y++) {
            arr[i] = new int[length];
            int a = x, b = y;
            for (int j = 0; j < length; j++) {
                arr[i][j] = grid[a][b];
                while (a + directions[d][0] < x || a + directions[d][0] > m - 1 - x
                        || b + directions[d][1] < y || b + directions[d][1] > n - 1 - y) {
                    d = (d + 1) % 4;
                }
                a += directions[d][0];
                b += directions[d][1];
            }
            int offset = k % length;
            a = x;
            b = y;
            d = 0;
            for (int j = offset; j < offset + length; j++) {
                grid[a][b] = arr[i][j % length];
                while (a + directions[d][0] < x || a + directions[d][0] > m - 1 - x
                        || b + directions[d][1] < y || b + directions[d][1] > n - 1 - y) {
                    d = (d + 1) % 4;
                }
                a += directions[d][0];
                b += directions[d][1];
            }
            length -= 8;
        }
        return grid;
    }

}

性能