旋转数组

一、定义与常见问题

旋转数组（rotated array）是指通过将一个数组的若干元素从头部移到数组尾部而得到的新数组。

常见的问题包括：在旋转数组中寻找最小值、在旋转数组中寻找目标值、在旋转数组中删除重复项等。

二、最小值问题

在旋转数组中寻找最小值是一个常见的问题。一个朴素的方法是遍历整个数组，时间复杂度为O(n)。但是，我们可以运用旋转数组的性质来降低时间复杂度。

由于最小值的左边和右边都比它大，因此可以用类似二分查找的方法来逼近最小值。具体思路如下：

class Solution {
public:
    int findMin(vector& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

  

三、目标值问题

在旋转数组中寻找目标值也是一个常见的问题。我们仍然可以运用二分查找的思路。具体思路如下：

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

  

四、删除重复项问题

在旋转数组中删除重复项同样是一个常见问题。我们可以运用双指针法来实现。具体思路如下：

class Solution {
public:
    int removeDuplicates(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        int slow = 1;
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow - 1]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

  

五、总结

旋转数组是一个常见的问题，我们可以运用其性质来实现各种操作。最小值问题和目标值问题都可以用二分查找来实现，而删除重复项问题可以用双指针法来实现。在实际应用中，需要灵活运用这些算法来解决各种问题。