shelterofly

目标

整数数组 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;
    }

}

性能