标签： 循环数组

目标

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

}

性能

目标

已知一个长度为 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];
    }

}

性能

目标

给你一个 环形 数组 nums 和一个数组 queries 。

对于每个查询 i ，你需要找到以下内容：

• 数组 nums 中下标 queries[i] 处的元素与 任意 其他下标 j（满足 nums[j] == nums[queries[i]]）之间的 最小 距离。如果不存在这样的下标 j，则该查询的结果为 -1 。

返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

示例 1：

输入： nums = [1,3,1,4,1,3,2], queries = [0,3,5]
输出： [2,-1,3]
解释：
查询 0：下标 queries[0] = 0 处的元素为 nums[0] = 1 。最近的相同值下标为 2，距离为 2。
查询 1：下标 queries[1] = 3 处的元素为 nums[3] = 4 。不存在其他包含值 4 的下标，因此结果为 -1。
查询 2：下标 queries[2] = 5 处的元素为 nums[5] = 3 。最近的相同值下标为 1，距离为 3（沿着循环路径：5 -> 6 -> 0 -> 1）。

示例 2：

输入： nums = [1,2,3,4], queries = [0,1,2,3]
输出： [-1,-1,-1,-1]
解释：
数组 nums 中的每个值都是唯一的，因此没有下标与查询的元素值相同。所有查询的结果均为 -1。

说明：

• 1 <= queries.length <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 0 <= queries[i] < nums.length

思路

有一个环形数组 nums 和一个查询数组 queries，返回 元素值与 queries[i] 相同的其它元素之间的最小距离，如果不存在则结果为 -1，返回查询结果数组。

根据元素值分组，分组内记录下标。针对每个查询，二分查找元素在分组中的位置，比较前后下标的距离，如果分组只有一个元素，返回 -1。需要特殊处理首与尾的最近距离。

也可以分组后预处理每个位置的最近距离，统一计算前后的最近距离，查询时直接取结果即可。注意循环数组的距离处理，这里直接将超出的距离映射回了原数组下标，因此最近距离需要取 min(d, n - d)，其中 d = abs(i - j) 表示下标 i 与 j 的距离。

代码

/**
 * @date 2026-04-16 8:55
 */
public class SolveQueries3488 {

    public List<Integer> solveQueries_v1(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        int[] dis = new int[n];
        for (List<Integer> list : map.values()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                int index = list.get(i);
                if (size >= 2) {
                    int prev = Math.abs(index - list.get((size + i - 1) % size));
                    int next = Math.abs(list.get((i + 1) % size) - index);
                    dis[index] = Math.min(Math.min(prev, n - prev), Math.min(next, n - next));
                } else {
                    dis[index] = -1;
                }
            }
        }
        List<Integer> res = new ArrayList<>(queries.length);
        for (int query : queries) {
            res.add(dis[query]);
        }
        return res;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 的次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101... 所需的反转次数 k，那么 10101010... 所需的反转次数为 n - k，参考 1758_生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

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

示例 2：

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

说明：

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

进阶：

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路

将 有序数组 划分为两个子数组，交换子数组的顺序得到旋转数组 nums，判断旋转数组中是否存在 target。

根据题意可知，原来的有序数组被划分成两部分，第一部分的所有元素均大于 等于 第二部分的所有元素。

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。如果当前元素恰好与切点的元素值相同，那么我们无法判断该搜索哪一部分。

例如，如果当前元素值大于 target，但是恰好与第一个元素相同：

• 如果当前元素就是位于第一部分，那么我们应该将 left 右移，以便到达第二部分搜索。
• 如果当前元素已经位于第二部分，那么我们应该将 right 左移，以便找到更小的target。

最简单的处理方法是缩小右边界，因为这种情况只会出现在切点刚好在连续相同元素中间，这时最左侧的元素一定与最右侧的元素相同，我们可以提前将 right 移到第一个与 left 不同的位置。这样当前元素属于哪一部分就确定了，不会影响判断。

代码

/**
 * @date 2025-02-01 14:33
 */
public class Search81 {

    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (right > 0 && nums[left] == nums[right]) {
            right--;
        }
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums[mid], nums[0], target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        if (left >= 0 && left < n) {
            return nums[left] == target;
        }
        return false;
    }

    public boolean check(int midValue, int firstValue, int target) {
        if (target < firstValue) {
            if (midValue >= firstValue) {
                return true;
            } else {
                return midValue < target;
            }
        } else {
            if (midValue >= firstValue) {
                return midValue < target;
            } else {
                return false;
            }
        }
    }

}

性能