剑指offer 面试题11旋转数组的最小数字+快速排序

快速排序
面试题11：旋转数组的最小数字

package com.cloud.algorithm.demo;

import org.junit.Test;

import java.util.Arrays;

/**
 * DATE: 2021/4/1
 * Author: xiaoqu
 * Version: 1.0.0
 */
public class Topic11 {

    /**
     * 快速排序
     */
    @Test
    public void topic11_1() {
        int[] arr = {3, 9, 4, 3, 11, 7, 1, 2, 8};
        this.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 面试题11：旋转数组的最小数字
     * 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素，
     * 例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小元素为1
     */
    @Test
    public void topic11_2() {

        /**
         * 旋转数组可以看成两个数组，数组A和数组B
         * 例如旋转数组为{3,4,5,1,2} 数组A为{3,4,5} 数组B为{1,2}
         * 数组的特点为数组A里面的任意元素大于等于数组B的元素
         * 解法为二分法：起始元素为i=0，结束元素为k=(length-1)中间元素为j=(i+k)/2 ，
         * 起始元素和中间元素比较，
         * 如果arr[i]<arr[j] 则 i=j ,k=(length-1), j=(i+k)/2
         * 且剩下的元素又为一个旋转数组，起始元素大于数组B的元素,
         * 一次循环，如果只剩两个元素，则
         *
         */
        int[] arr = {2, 0, 2, 2, 2, 2, 2};

        int i = this.demo01(arr, 0, arr.length - 1);
        System.out.println(i);


    }

    public int demo01(int arr[], int startIdx, int endIdx) {
        while (true) {

            if (endIdx - startIdx == 1) {
                break;
            } else {
                int midIdx = (endIdx + startIdx) / 2;

                if (arr[startIdx] == arr[midIdx] && arr[midIdx] == arr[endIdx]) {
                    //这里不能排序了，只能顺序比较
                    int i = this.demo01_1(arr, startIdx, endIdx);
                    return i;
                }

                if (arr[startIdx] < arr[endIdx]) {
                    //如果第一个数大于最后一个数则表示已排好序
                    endIdx = startIdx;
                    break;
                }
                if (arr[midIdx] >= arr[startIdx]) {
                    startIdx = midIdx;
                } else if (arr[midIdx] <= arr[endIdx]) {
                    endIdx = midIdx;
                }
            }
        }
        return arr[endIdx];
    }

    private int demo01_1(int arr[], int startIdx, int endIdx) {
        int temp = arr[startIdx];
        for (int i = startIdx; i <= endIdx; i++) {
            temp = arr[i] > temp ? temp : arr[i];
        }
        return temp;
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param startIdx
     * @param endIdx
     */
    public void quickSort(int[] arr, int startIdx, int endIdx) {
        int i = startIdx, j = endIdx;
        if (startIdx < endIdx) {
            int temp = arr[i];
            while (i < j) {
                while (i < j && arr[j] >= temp) {
                    j--;
                }
                arr[i] = arr[j];
                while (i < j && arr[i] <= temp) {
                    i++;
                }
                arr[j] = arr[i];
            }
            arr[i] = temp;
            quickSort(arr, startIdx, i - 1);
            quickSort(arr, i + 1, endIdx);
        }
    }

}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118