C#LeetCode刷题之#485-最大连续1的个数(Max Consecutive Ones)

C#LeetCode刷题之#485-最大连续1的个数(Max Consecutive Ones)

问题

给定一个二进制数组, 计算其中最大连续1的个数。

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

注意:
输入的数组只包含 0 和1。
输入数组的长度是正整数,且不超过 10,000。

Given a binary array, find the maximum number of consecutive 1s in this array.

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.The maximum number of consecutive 1s is 3.

Note:
The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums = null;

        nums = new int[] { 1, 1, 0, 1, 1, 1 };
        var res = FindMaxConsecutiveOnes(nums);
        Console.WriteLine(res);

        res = FindMaxConsecutiveOnes2(nums);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int FindMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int max = 0;
        for(int i = 0; i < nums.Length; i++) {
            if(nums[i] == 0) {
                if(count > max) max = count;
                count = 0;
            } else {
                count++;
            }
        }
        return count > max ? count : max;
    }

    private static int FindMaxConsecutiveOnes2(int[] nums) {
        //同FindMaxConsecutiveOnes,只是写法稍微好看一点
        int max = 0;
        for(int i = 0, count = 0; i < nums.Length; i++) {
            count = nums[i] == 1 ? count + 1 : 0;
            max = count > max ? count : max;
        }
        return max;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

3
3

分析:

显而易见,以上2种算法的时间复杂度均为: O(n)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3714

发表评论

登录后才能评论