Eric's Blogs

Better Code, Better Life

0%

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

四个方向,一圈一圈分别处理;最后处理单行,单列的情况

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
public ArrayList<Integer> printMatrix(int[][] matrix) {
    ArrayList<Integer> ans = new ArrayList<>();
    int row = matrix.length, col = matrix[0].length;

    int circle = 0;
    int stepCol = col - 1, stepRow = row - 1;

    while (col - circle * 2 > 1 && row - circle * 2 > 1) {
        int start1 = circle;
        for (int i = start1; i < stepCol + start1; i++) {
            ans.add(matrix[circle][i]);
        }
        int start2 = circle;
        for (int j = start2; j < stepRow + start2; j++) {
            ans.add(matrix[j][col - circle - 1]);
        }
        int start3 = col - circle - 1;
        for (int i = start3; i > start3 - stepCol; i--) {
            ans.add(matrix[row - circle - 1][i]);
        }
        int start4 = row - circle - 1;
        for (int j = start4; j > start4 - stepRow; j--) {
            ans.add(matrix[j][circle]);
        }
        stepCol -= 2;
        stepRow -= 2;
        circle++;
    }
    if (row - circle * 2 == 1 && col - circle * 2 == 1) {
        /** 处理最后剩一个的问题 */
        ans.add(matrix[row / 2][col / 2]);
    } else {
        if (col - circle * 2 == 1) {
            /** 处理单列 */
            for (int i = circle; i < row - circle; i++) {
                ans.add(matrix[i][col / 2]);
            }
        }
        if (row - circle * 2 == 1) {
            /** 处理单行 */
            for (int j = circle; j < col - circle; j++) {
                ans.add(matrix[row / 2][j]);
            }
        }
    }

    return ans;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a?answerType=1&f=discussion
来源：牛客网

1. 分析

刷 LeetCode 看到的大神题解，感觉容易理解且好写
简单来说，就是不断地收缩矩阵的边界
定义四个变量代表范围，up、down、left、right

  1. 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
  2. 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
  3. 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
  4. 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错

2. 代码

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
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return list;
        }
        int up = 0;
        int down = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        while(true){
            // 最上面一行
            for(int col=left;col<=right;col++){
                list.add(matrix[up][col]);
            }
            // 向下逼近
            up++;
            // 判断是否越界
            if(up > down){
                break;
            }
            // 最右边一行
            for(int row=up;row<=down;row++){
                list.add(matrix[row][right]);
            }
            // 向左逼近
            right--;
            // 判断是否越界
            if(left > right){
                break;
            }
            // 最下面一行
            for(int col=right;col>=left;col--){
                list.add(matrix[down][col]);
            }
            // 向上逼近
            down--;
            // 判断是否越界
            if(up > down){
                break;
            }
            // 最左边一行
            for(int row=down;row>=up;row--){
                list.add(matrix[row][left]);
            }
            // 向右逼近
            left++;
            // 判断是否越界
            if(left > right){
                break;
            }
        }
        return list;
    }
}

3. 复杂度

时间复杂度：img
空间复杂度：img

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

注意子结构和子树的区别

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
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root2 == null) {
        return false;
    }
    List<TreeNode> treeNodeList = getNode(root2.val, root1);

    for (TreeNode treeNode : treeNodeList) {
        if (judgeTree(treeNode, root2)) {
            return true;
        }
    }
    return false;
}

/**
 * 判断子结构
 */
boolean judgeTree(TreeNode r1, TreeNode r2) {

    if (r2 == null) {
        return true;
    }
    if (r1 == null) {
        return false;
    }
    if (r1.val != r2.val) {
        return false;
    }
    return judgeTree(r1.left, r2.left) && judgeTree(r1.right, r2.right);
}

/**
 * 找到所有值相同的节点
 */
List<TreeNode> getNode(int var, TreeNode root) {
    List<TreeNode> ans = new ArrayList<>();

    Stack<TreeNode> stack = new Stack<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.empty()) {
        TreeNode tmp = stack.pop();
        if (tmp.val == var) {
            ans.add(tmp);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
    }
    return ans;
}

发表于 分类于
本文字数： 701 阅读时长 ≈ 1 分钟

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

1
2
3
4
5
6
7
8
9
10
11
12
二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

递归最简单

1
2
3
4
5
6
7
8
9
10
11
public void Mirror(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode left = root.left;
    root.left = root.right;
    root.right = left;

    Mirror(root.left);
    Mirror(root.right);
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void Mirror(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode tmp = stack.pop();
        TreeNode left = tmp.left;
        tmp.left = tmp.right;
        tmp.right = left;
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
    }
}

发表于 更新于 分类于
本文字数： 644 阅读时长 ≈ 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
public ListNode Merge(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    ListNode head = null, pre = null;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            if (head == null) {
                head = list1;
                pre = head;
            } else {
                pre.next = list1;
                pre = list1;
            }
            list1 = list1.next;
        } else {
            if (head == null) {
                head = list2;
                pre = head;
            } else {
                pre.next = list2;
                pre = list2;
            }
            list2 = list2.next;
        }
    }
    pre.next = (list1 != null) ? list1 : list2;
    return head;
}

todo:还可以用递归的方式

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

非递归快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double Power(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    if (exponent < 0) {//负数次幂
        base = 1.0 / base;
        exponent = -exponent;
    }
    double ans = 1.0, tmpEx = base;
    while (exponent > 0) {
        if ((exponent & 0x01) == 1) {
            ans *= tmpEx;
        }
        tmpEx *= tmpEx;//翻倍
        exponent = exponent >> 1;
    }
    return ans;
}

网上解法

链接：https://www.nowcoder.com/questionTerminal/1a834e5e3e1a4b7ba251417554e07c00?answerType=1&f=discussion
来源：牛客网

预处理：求pow(b, n)，如果n为负数怎么解决？

假如求图片说明 ,是不是可以转换成图片说明
于是，预处理代码如下：

1
2
3
4
5
6
double Power(double b, int n) {
    if (n < 0) {
        b = 1 / b;
        n = -n;
     }
}

方法一：暴力方法

很显然就是n个b相乘。循环n次。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double ret = 1.0;
        for (int i=0; i<n; ++i) ret *= b;
        return ret;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

方法二：递归法（快速幂）

假设我们求图片说明 ，如果我们知道图片说明 ，那么图片说明 ，所以图片说明

但是还有个小问题，如果n是偶数，那么上述没问题。

如果n是奇数，图片说明 ， 比如图片说明
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double q_power(double b, int n) {
        if (n == 0) return 1.0;
        double ret = q_power(b, n/2);
        if (n&1) { // 奇数
            return ret * ret * b;
        }
        else {
            return ret * ret;
        }
    }
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        return q_power(b, n);
    }
};

时间复杂度：O(logn)，每次规模减少一半
空间复杂度：O(logn)，递归栈，因为要记住logn个变量

方法三：非递归的快速幂

假设求图片说明 ,已知6可以表示成二进制110
可以表示成图片说明 ,所以图片说明 可以表示成图片说明 所以，对于二进制数，遇到位数是1的就乘到答案中。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:

    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double x = b; // 记录x^0, x^1, x^2 ...
        double ret = 1.0;
        while (n) {
            if (n&1) {
                ret *= x; // 二进制位数是1的，乘进答案。
            }
            x *= x;
            n >>= 1;
        }
        return ret;
    }
};

上述方法相当于遍历n的二进制位，是1就乘进结果
时间复杂度：O(logn)，因为n的二进制位个数为logn
空间复杂度：O(1)

拓展

STL标准库中，pow函数的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T,class Integer, class MonoidOperation>
T power_this(T x, Integer n, MonoidOperation op){ // 可以看成求pow(x, n)
    if (n == 0)
        return identity_element(op); // 可以看成 1
    else{
        while ((n & 1) == 0){
            n >>= 1;
            x = op(x, x); //op看成乘法
        }
        T result = x; // 遇到 二进制中从低位到高位的第一个 1
        n >>= 1;
        while (n != 0){
            x = op(x, x);
            if ((n & 1) != 0)
                result = op(result, x);
            n >>= 1;
        }
        return result;
    }
}

做法跟我们方法三是一样的。

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

空间换时间,时间复杂度O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void reOrderArray(int [] array) {
    int[] ans = new int[array.length];
    int[] oddList = new int[array.length];
    int[] evenList = new int[array.length];
    int oddNum = 0, evenNum = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] % 2 == 1) {
            oddList[oddNum++] = array[i];
        } else {
            evenList[evenNum++] = array[i];
        }
    }
    for (int k = 0; k < oddNum; k++) {
        ans[k] = oddList[k];
    }
    for (int k = 0; k < evenNum; k++) {
        ans[k + oddNum] = evenList[k];
    }

    for (int i = 0; i < ans.length; i++) {
        array[i] = ans[i];
    }
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593?answerType=1&f=discussion
来源：牛客网

思路：参考快速排序

  • i++往前走碰到偶数停下来，j = i+1
  • 若a[j]为偶数，j++前进，直到碰到奇数
  • a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
  • 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动

图片说明 

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:
    void reOrderArray(vector<int> &array) {
        int len = array.size();
        if(len <= 1){ // 数组空或长度为1
            return;
        }

        int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                while(array[j]%2 == 0){ // j为偶数，前进
                    if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                         return;
                    j++;
                }
                // 此时j为奇数
                int count = j-i;
                int temp = array[i];
                array[i] = array[j];
                while(count>1){
                    array[i+count] = array[i+count-1];//数组后移
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }
};

发表于 分类于
本文字数： 381 阅读时长 ≈ 1 分钟

题目描述

输入一个链表，反转链表后，输出新链表的表头。

三个指针操作,注意将原链表的head.next置为null,同时注意处理原链表为空的情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode ReverseList(ListNode head) {
    if (head==null||head.next == null) {
        return head;
    }
    ListNode pre=head,cur=head.next,next=head.next.next;
    head.next=null;//容易忘!
    while (true){
        cur.next=pre;
        pre=cur;
        cur=next;
        if (cur==null){
            break;
        }
        next=cur.next;
    }
    return pre;
}

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

输入一个链表，输出该链表中倒数第k个结点。

两个指针即可,注意处理k=0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode FindKthToTail(ListNode head, int k) {
    if (head == null || k < 1) {
        return null;
    }
    ListNode kth = null;
    ListNode tmp = head;
    for (int i = 0; i < k - 1 && tmp != null; i++) {
        tmp = tmp.next;
    }
    if (tmp == null) {
        return null;
    }
    kth = head;

    for (; tmp.next != null; tmp = tmp.next) {
        kth = kth.next;
    }

    return kth;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a?answerType=1&f=discussion
来源：牛客网

解法 1: 两次循环

因为要求链表倒数第 k 个节点，也就是求正数第length - k个节点。整体过程如下：

  • 链表又是个单链表，并且没有保存长度信息。所以需要循环一次计算length。
  • 第二次循环找到第length - k个节点。

时间复杂度是 O(N)，需要 2 次循环。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21


function FindKthToTail(head, k) {
    let length = 0;
    let node = head;
    while (node) {
        ++length;
        node = node.next;
    }

    if (k > length) {
        return null;
    }

    node = head;
    let offset = length - k;
    for (let i = 0; i < offset; ++i) {
        node = node.next;
    }
    return node;
}

解法 2: 快慢(双)指针

准备两个指针：left（慢）和 right（快）。整体过程如下：

  • right 先向右移动 k 位，此时 index(right) - index(left) = k
  • left 和 right 一起向右移动，直到 right 抵达边界
  • 由于index(right) - index(left) = k，所以index(left) = index(right) - k = length - k。也就是 left 指针移动到了倒数第 k 个位置

时间复杂度是 O(N)，但仅需要遍历一次。空间复杂度是 O（1）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function FindKthToTail(head, k) {
    let right = head;
    for (let i = 0; i < k; ++i) {
        if (right === null) {
            // 链表长度小于k
            return null;
        }
        right = right.next;
    }

    let left = head;
    while (right) {
        left = left.next;
        right = right.next;
    }

    return left;
}

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

递归建树即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if (pre == null || pre.length == 0) {
        return null;
    }
    TreeNode root = new TreeNode(pre[0]);
    int rootInMid = 0;
    for (int i = 0; i < in.length; i++) {
        if (in[i] == pre[0]) {
            rootInMid = i;
            break;
        }
    }
    /** 左子树结点个数 */
    int leftNum = rootInMid;

    root.left = reConstructBinaryTree(
        Arrays.copyOfRange(pre, 1, leftNum + 1),
        Arrays.copyOfRange(in, 0, rootInMid));
    root.right = reConstructBinaryTree(
        Arrays.copyOfRange(pre, leftNum + 1, pre.length),
        Arrays.copyOfRange(in, rootInMid + 1, in.length));

    return root;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6?answerType=1&f=discussion
来源：牛客网

递归构建二叉树

1. 分析

根据中序遍历和前序遍历可以确定二叉树，具体过程为：

  1. 根据前序序列第一个结点确定根结点
  2. 根据根结点在中序序列中的位置分割出左右两个子序列
  3. 对左子树和右子树分别递归使用同样的方法继续分解

例如：
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in

  1. 根据当前前序序列的第一个结点确定根结点，为 1
  2. 找到 1 在中序遍历序列中的位置，为 in[3]
  3. 切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树
  4. 则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6}
  5. 对子树分别使用同样的方法分解

2. 代码

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
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }
}

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

O(n)的复杂度,不够好,应该参考二分查找的实现.

1
2
3
4
5
6
7
8
9
10
11
public int minNumberInRotateArray(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    }
    for (int i = array.length - 1; i > 0; i--) {
        if (array[i - 1] > array[i]) {
            return array[i];
        }
    }
    return array[0];
}

改进版,要考虑到1,1,0,1,1,1,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
if (array == null || array.length == 0) {
    return 0;
}

int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
/** 答案一定在start,mid,end的最大值和最小值之间 */
for (; array[start] >= array[end] && end - start >= 2; mid = (start + end) / 2) {//说明有接头处
    if (array[mid] < array[start] || array[mid] < array[end]) {
        end = mid;
    } else if (array[mid] > array[start] || array[mid] > array[end]) {
        start = mid;
    } else {//start,mid,end相等的特殊情况
        int min = Integer.MAX_VALUE;
        for (int i = start; i < end; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}

return Math.min(array[start], array[end]);

网上题解

链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion
来源：牛客网

直接进行顺序的查找,复杂度为O(n).
但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).
这里我们需要利用带有条件的二分法来进行求解:

第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2.

第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的位置.

第三步,当我们的 end 所对应的值大于 mid 所对应的值时,说明最小值可能是 mid 所对应的值或者在 mid 的前面,我们将 end 移到 mid 所在的位置.

第四步,最后我们的 end 所在的位置就是最小值的位置,直接返回即可.

我说下,在牛客的这道题目中,以上的方法就可以提交完成,但是当我们看剑指offer的书时,有这样的特例 比如数组 10111 , 这是会出现当 start mid end 所对应位置的值相等,这时候我们的程序就不能找到最小值,当出现这样的情况时,我们采用将 start 和 end 区间里面的值进行顺序查找来找出最小值.

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
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if len(rotateArray) == 1:
            return rotateArray[0]
        start = 0
        end = len(rotateArray)-1

        while rotateArray[start] >= rotateArray[end]:
            if end - start == 1:
                break
            mid = (start + end) // 2
            if rotateArray[start] == rotateArray[mid] and rotateArray[end] == rotateArray[mid]:
                #进行顺序查找
                temp = rotateArray[start]
                for i in range(start,end + 1):
                    if temp < rotateArray[i]:
                        temp = rotateArray[i]
                return temp
            if rotateArray[mid] >= rotateArray[start]:
                start = mid
            elif rotateArray[end] >= rotateArray[mid]:
                end = mid
        return rotateArray[end]