搜索旋转数组相关

发表于 | 分类于 ， ， |

189.旋转数组、寻找旋转排序数组中的最小值 I、寻找旋转排序数组中的最小值 II、搜索旋转排序数组 I、搜索旋转排序数组 II、面试题 10.03.搜索旋转数组

189.旋转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k = k%n;

        //先整个翻转
        reverse(nums, 0, n-1);
        //翻转前k个
        reverse(nums, 0, k-1);
        //翻转后n-k个
        reverse(nums, k, n-1);
    }
    void reverse(vector<int>& nums, int start, int end){
        while(start<end){
            int temp=nums[start];
            nums[start++]=nums[end];
            nums[end--]=temp;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func rotate(nums []int, k int) {
    n := len(nums)
    k = k % n

    //先整个翻转
    reverse(nums, 0, n-1)
    //翻转前k个
    reverse(nums, 0, k-1)
    //翻转后n-k个
    reverse(nums, k, n-1)
}

func reverse(nums []int, start, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

153.寻找旋转排序数组中的最小值 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMin(vector<int>& nums) {
        //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left < right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[right]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findMin(nums []int) int {
    //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
    n := len(nums)
    left := 0
    right := n - 1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < nums[right] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return nums[left]
}

154.寻找旋转排序数组中的最小值 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int>& nums) {
        //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[right]){
                left=mid+1;
            }else if(nums[mid]<nums[right]){
                right=mid;
            }else{
                //将right左移一位
                right=right-1;
            }
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func findMin(nums []int) int {
    //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
    n := len(nums)
    left := 0
    right := n - 1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            //将right左移一位
            right = right - 1
        }
    }
    return nums[left]
}

33.搜索旋转排序数组

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0) return -1;

        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;

            //右半部分是有序的
            if(nums[n-1]>nums[mid]){ 
                //target落在右半部分有序区域内
                if(nums[mid]<target && target<=nums[n-1]){
                    left = mid+1;
                }else{ //target落在左半部分无序区域内
                    right = mid-1;
                }
            }else{//左半部分是有序的
                //target落在左半部分有序区域内
                if(nums[0]<=target && target<nums[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }
        }
        return -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
func search(nums []int, target int) int {
    n := len(nums)
    if n == 0 {
        return -1
    }

    left := 0
    right := n - 1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }

        //右半部分是有序的
        if nums[n-1] > nums[mid] {
            //target落在右半部分有序区域内
            if nums[mid] < target && target <= nums[n-1] {
                left = mid + 1
            } else { //target落在左半部分无序区域内
                right = mid - 1
            }
        } else { //左半部分是有序的
            //target落在左半部分有序区域内
            if nums[0] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                //target落在右半部分无序区域内
                left = mid + 1
            }
        }
    }
    return -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
//解法二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int k=1;
        while(k<n && nums[k] >= nums[k-1]) k++;
        int res=-1;

        int left_val = BinarySearch(nums, target, 0, k-1);
        int right_val = BinarySearch(nums, target, k, n-1);

        if(left_val!=-1) res=left_val;
        if(right_val!=-1) res=right_val;

        return res;
    }
    //二分查找
    int BinarySearch(vector<int>& nums, int target, int low, int high){
        int n=nums.size();
        int left=low;
        int right=high;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return -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
38
//解法二
func search(nums []int, target int) int {
    n := len(nums)
    k := 1
    for k < n && nums[k] >= nums[k-1] {
        k++
    }
    res := -1

    left_val := binarySearch(nums, target, 0, k-1)
    right_val := binarySearch(nums, target, k, n-1)

    if left_val != -1 {
        res = left_val
    }
    if right_val != -1 {
        res = right_val
    }

    return res
}

//二分查找
func binarySearch(nums []int, target, low, high int) int {
    left := low
    right := high
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

81.搜索旋转排序数组 II

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:
    bool search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0) return false;
        int left=0;
        int right=n-1;
        while(left<=right){
            //重点在于处理重复数字
            //左边有重复数字，将左边界右移
            while(left<right && nums[left]==nums[left+1]) left++;
            //右边有重复数字，将右边界左移
            while(left<right && nums[right]==nums[right-1]) right--;
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return true;
            //左半部分是有序
            if(nums[0]<=nums[mid]){
                //target落在左半部分有序区域内
                if(nums[0]<=target && target<nums[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }else{ //右半部分是有序
                //target落在右半部分有序区域内
                if(nums[mid]<target && target<=nums[n-1]){
                    left = mid+1;
                }else{
                    //target落在左半部分无序区域内
                    right = mid-1;
                }
            }
        }
        return false;
    }
};
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
func search(nums []int, target int) bool {
    n := len(nums)
    if n == 0 {
        return false
    }
    left := 0
    right := n - 1
    for left <= right {
        //重点在于处理重复数字
        //左边有重复数字，将左边界右移
        for left < right && nums[left] == nums[left+1] {
            left++
        }
        //右边有重复数字，将右边界左移
        for left < right && nums[right] == nums[right-1] {
            right--
        }
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }
        //左半部分是有序
        if nums[0] <= nums[mid] {
            //target落在左半部分有序区域内
            if nums[0] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                //target落在右半部分无序区域内
                left = mid + 1
            }
        } else { //右半部分是有序
            //target落在右半部分有序区域内
            if nums[mid] < target && target <= nums[n-1] {
                left = mid + 1
            } else {
                //target落在左半部分无序区域内
                right = mid - 1
            }
        }
    }
    return false
}

面试题 10.03.搜索旋转数组

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:
    int search(vector<int>& arr, int target) {
        int n=arr.size();
        int left=0;
        int right=n-1;
        while(left<=right){
            //当left符合时直接返回，因为找的是最小的索引
            if(arr[left]==target) return left;

            int mid=left+(right-left)/2;
            //当中间值等于target，将右边界移到中间，因为左边可能还有相等的值
            if(arr[mid]==target){
                right=mid;
            }else if(arr[0]<arr[mid]){      //左半部分是有序
                //target落在左半部分有序区域内
                if(arr[0]<=target && target<arr[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }else if(arr[0]>arr[mid]){ //右半部分是有序
                //target落在右半部分有序区域内
                if(arr[mid]<target && target<=arr[n-1]){
                    left = mid+1;
                }else{
                    //target落在左半部分无序区域内
                    right = mid-1;
                }
            }else{
                //当中间数字与左边数字相等时，将左边界右移
                left=left+1;
            }
        }
        return -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
func search(arr []int, target int) int {
    n := len(arr)
    left := 0
    right := n - 1
    for left <= right {
        //当left符合时直接返回，因为找的是最小的索引
        if arr[left] == target {
            return left
        }

        mid := left + (right-left)/2
        //当中间值等于target，将右边界移到中间，因为左边可能还有相等的值
        if arr[mid] == target {
            right = mid
        } else if arr[0] < arr[mid] { //左半部分是有序
            //target落在左半部分有序区域内
            if arr[0] <= target && target < arr[mid] {
                right = mid - 1
            } else {
                //target落在右半部分无序区域内
                left = mid + 1
            }
        } else if arr[0] > arr[mid] { //右半部分是有序
            //target落在右半部分有序区域内
            if arr[mid] < target && target <= arr[n-1] {
                left = mid + 1
            } else {
                //target落在左半部分无序区域内
                right = mid - 1
            }
        } else {
            //当中间数字与左边数字相等时，将左边界右移
            left = left + 1
        }
    }
    return -1
}
-------------本文结束 感谢阅读-------------
0%