5. 找出旋转有序数列的中间值

2020-09-05

XMOJ

数学

3 分钟读完 (大约 442 个字) 0次访问

XMOJ 5. 找出旋转有序数列的中间值

描述:

给出一个有序数列随机旋转之后的数列，如原有序数列为：[0,1,2,4,5,6,7] ，旋转之后为[4,5,6,7,0,1,2]。假定数列中无重复元素，且数列长度为奇数。求出旋转数列的中间值。如数列[4,5,6,7,0,1,2]的中间值为4。

输入:

4,5,6,7,0,1,2

输出:

4

输入样例:

1
1,2,3
4,5,6,7,0,1,2
12,13,14,5,6,7,8,9,10

输出样例:

1
2
4
9

方法：数学

思路：通过一次循环找到数列中最大数字的索引maxIndex，通过以下公式即可得到中间值的索引：(maxIndex + n / 2 + 1) % n，n为数列的长度。

运行数据：最大执行时间：87.20 ms，最大内存开销：17356 KiB

复杂度分析：

由于输入数据组数无法确定，时间复杂度和空间复杂度只考虑一组数据。

时间复杂度：O(n)，n为一组输入数据的个数，循环一次输入数据。
空间复杂度：O(n)，n为一组输入数据的个数，主要为保存拆分字符串的字符串数组的空间消耗。

import java.util.Scanner;

public class Main {
    
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String line;
        while (scan.hasNextLine()) {
            line = scan.nextLine().trim();
            String[] strs = line.split(",");
            int n = strs.length;
            int pre = Integer.MIN_VALUE;
            int maxIndex = 0;
            for (int i = 0; i < n; i++) {
                int current = Integer.valueOf(strs[i]);
                if (current < pre) {
                    break;
                }
                pre = current;
                maxIndex = i;
            }
            System.out.println(strs[(maxIndex + n / 2 + 1) % n]);
        }
    }
}