时间戳

首页 > 解决方案 > O(n) 中的连续子阵列解决方案

algorithm - O(n) 中的连续子阵列解决方案

问题描述

最近我遇到一个问题，说明有一个整数数组，我们将得到一个通配符数字。我们需要查看数组并形成一个子数组，使得

  1. 通配符编号应该是子数组的最后一个元素（即：如果 4 是通配符编号但 {2,4,3} 无效，则 {2,3,4} 有效）。
  2. 通配符编号之前的所有元素都应小于该值。（即：如果 4 是通配符号码，{2,3,4} 有效，但 {5,2,4} 无效）。
  3. 通配符号码不应该在两个子数组之间出现。

输出应返回此类子数组的长度。

示例问题：如果数组是 {4,5,6,4,3,2,4,8,2,4} 并且通配符编号是 4，则输出应该是 7。（因为子数组是 {4} ，{4}，{3,2,4}，{2,4}）。

我已经为这个问题编写了代码。但我需要知道的是解决方案是否可以写成 O(n) 时间复杂度。还有一种方法可以通过单独查看问题来找到可能的最佳时间复杂度。

代码片段：

private static void solution(int[] array, int k)
    {
        int forwardCounter = 0;
        int backwardCounter = 0;
        int length = 0;

        while(forwardCounter != array.length)
        {
            if(array[forwardCounter] == k)
            {
                length++;
                backwardCounter = forwardCounter - 1;
                while(backwardCounter >= 0)
                {
                    if(backwardCounter >= 0 && array[backwardCounter--] < k)
                    {
                        length++;
                    }
                    else
                        break;
                }
            }
            forwardCounter++;
        }
        System.out.println(length);
    }

    public static void main(String[] args) 
    {
        solution(new int[]{4,5,6,4,3,2,4,8,2,4}, 4);
    }

标签： algorithmtime-complexity

解决方案

您的解决方案是线性的，但在最坏的情况下，您的数组将被遍历两次。
当 -array按升序排序时，最坏的情况显然会发生
-wildcard number 是 array 的最后一个（即最大）元素

可以修改您的解决方案以防止向后遍历并仅使用前向遍历。

推荐阅读