By

文章目錄

最近又把冼镜光的《C语言名题精选百则–技巧篇》拿出来看看，确实不错。

已知一个已经从小到大排序的数组，这个数组中的一个平台(plateau) 就是连续的一串相同的元素，并且这一串元素不能再延伸。例如，在1，2，2，3，3，3，4，5，5，6中1，2.2，3.3.3，4，5.5，6都是平台。试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在上面的例子中，3.3.3就是该数组的最长平台。
这个问题曾经困扰过计算机科学家David Gries，他给出的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - length]) {
                length++;
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

自己想到的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        int i = 0;
        while (i + length < nums.length) {
            if (nums[i] == nums[i + length]) {
                length++;
            } else {
                i += length;
                while (i < nums.length && i > 0 &&  nums[i] == nums[i - 1]) {
                    i--;
                }
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

打赏作者

文章目錄