当前位置: 首页 > 面试题库 >

在数组中找到局部最小值

宦炜
2023-03-14
问题内容

给定一个整数数组和一个整数 k,从所有大小为 K 的连续子数组中找出 的最大元素。

例如:

Input : int[] arr = {2,6,-1,2,4,1,-6,5}
int k = 3
output : 6,6,4,4,4,5

对于每个大小为 k 的子数组,打印其最大元素。


问题答案:

基本的解决方案是生成所有大小为k的连续子数组并循环遍历它们以找出当前子数组中的最大值。考虑到,对于每个点,我们基本上都是取下一个 'k' 元素,然后我们遍历那些 k 个元素,因此该算法的最坏时间复杂度将是O(n*k)

package Arrays;

import java.util.Scanner;

public class slidingWindowMax {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int [] arr = new int[scn.nextInt()];

        for(int i = 0; i < arr.length; i++)
        {
            arr[i] = scn.nextInt();
        }

        int windowSize = scn.nextInt();

        solve(arr, windowSize);

    }

    public static void solve(int[] arr, int k)
    {
        // starting the outer loop from k and running it until, 
                // current pointer is EQUAL to arr.length
        for(int i = k; i <= arr.length; i++)
        {
            int max = Integer.MIN_VALUE;

            // this loop considers subarrays of size k ending at i-1
            for(int j = i-k; j<i; j++)
            {
                max = Math.max(max, arr[j]);
            }

            System.out.println(max);
        }
    }
}

稍微有效的方法:

通过使用Segment 树,我们肯定可以减少为每个子数组寻找最大值所花费的时间。
我们可以为给定的数组实现一个段树,我们可以通过范围查询[i, i+k-1]获取每个子数组的最大值。

段树中的节点总数:
构建段树的最坏时间复杂度为O(n),因为我们知道,
(i) 段树的叶节点包含数组的所有元素。
(ii) 最后一层的节点数是所有上一层的节点数。
在数学上,
考虑数组的长度为 n,因此,线段树的叶节点将为 n。
因此,所有上层的节点数将为 n-1。
长度为 n 的数组的段树上的总节点数为:

Tn = leaf nodes + nodes on upper levels
      = n + n-1
      = 2n+1

复杂性分析
我们的线段树的构建只涉及对每个节点的计算一次,因此构建线段树的最坏时间复杂度将是 O(2n+1) 即O(n)。
每个子数组的范围查询的结果将在O(logk) 中计算。
将对所有大小为 k 的“n-k+1”个子数组进行查询计算。
因此该算法的整体时间复杂度为 O((n-k+1)*logk) 即O(nlogk)。

package Arrays;

import java.util.Scanner;

public class slidingWindowMax {

    static int[] sarr;

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        int windowSize = scn.nextInt();

        int height = (int)Math.ceil((Math.log(arr.length) / Math.log(2)));

        /* size of segment array  i.e. the number of nodes will be = [(2^height+1)-1] */

        sarr = new int[1<<height -1];

        construct(0, 0, arr.length-1, arr);

        solve(arr, windowSize);

    }

    public static void solve(int[] arr, int k) {
        for (int i = 0; i <= arr.length - k; i++) {
            /* finding the result for range query from i to i+k which is basically a subarray.
             * 
             */
            System.out.println(query(0, i, i + k - 1, 0, arr.length - 1));
        }
    }

    public static int construct(int idx, int start, int end, int[] arr) {
        /* leaf nodes contains the array elements */
        if (start == end) {
            sarr[idx] = arr[end];
            return sarr[idx];
        }

        int mid = (start + end) / 2;
        /* dividing the range for every node in segment tree into two halves */
        int left = construct(2 * idx + 1, start, mid, arr);
        int right = construct(2 * idx + 2, mid + 1, end, arr);
        /* result for current index in segment tree will be calculated
         *  in post order, and will be maximum of its two childs.
         */
        sarr[idx] = Math.max(left, right);
        return sarr[idx];
    }

    public static int query(int idx, int queryStart, int QueryEnd, int start, int end) {
        /* if our range is completely outside the query, 
         * we need to return a result such that it causes no effect in our final answer.
         */

        if (start > QueryEnd || end < queryStart) {
            return Integer.MIN_VALUE;
        } 
        /* if the range of the current segment falls completely
         *  inside the query then return its value.
         */
        else if (start >= queryStart && end <= QueryEnd) {
            return sarr[idx];
        } else {

            int mid = (start + end) / 2;
            int left = query(2 * idx + 1, queryStart, QueryEnd, start, mid);
            int right = query(2 * idx + 2, queryStart, QueryEnd, mid + 1, end);

            return Math.max(left, right);
        }
    }
}

最有效的方法:

在这种方法中,我们使用Deque帮助我们找到O(n) 中的滑动窗口最大值。

Deque基本上是一个队列,其是在两个两个排队和deque,即,可以添加或删除元素或者从前面或后面的端部开放。
我们实际解决问题的方法是:

我们以相反的顺序保留子数组的 k 个元素,我们不需要保留所有的 k 个元素,尽管我们稍后会在代码中看到。

为前 k 个元素生成 Deque,保持它们以相反的顺序排序,以便最大元素位于最前面。
如果 Deque 为空,则直接添加元素,否则检查传入元素是否大于最后一个元素,如果是,则继续从最后一个元素弹出元素,直到剩余 Deque 的最后一个元素大于传入元素。
我们还需要删除属于不同子数组的元素。即 Deque 中的索引必须在[i, i+k]范围内。
一个元素只会在两种情况下被删除:
(i)如果即将到来的元素大于后部 元素,如果它,它将继续弹出元素,直到剩余出队的后部出现更大的元素,因为我们需要保持数组以相反的顺序排序
(ii) 如果元素属于任何其他子数组,则保留它没有意义。

package org.arpit.java2blog;

import java.util.LinkedList;
import java.util.Scanner;

public class SlidingWindowMax {

    static int[] sarr;

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");

        int windowSize = scn.nextInt();

        solveEfficient(arr, windowSize);

    }

    public static void solveEfficient(int[] arr, int k) {
        LinkedList<Integer> deque = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {

            /* keep removing the elements from deque 
             * which are smaller than the current element, 
             * because we need to keep our deque sorted in dec order 
             */
            while (!deque.isEmpty() && arr[deque.getLast()] <= arr[i]) {
                deque.removeLast();
            }

            /* removing the i-k element, because that element does not belong 
             * to the subarray we are currently working on.
             */
            while (!deque.isEmpty() && deque.getFirst() <= i - k) {
                deque.removeFirst();
            }

            deque.addLast(i);

            if(i >= k-1)
            {   
            /* only print when we have processed atleast k elements 
             * to make the very first subarray
             */
                System.out.print(" "+arr[deque.getFirst()]);
            }

        }
    }
}

当你运行上面的程序时,你会得到以下输出:

8
2 6 -1 2 4 1 -6 5
arr[]: { 2 6 -1 2 4 1 -6 5 }
3
6 6 4 4 4 5


 类似资料:
  • 问题内容: 你能否建议使用中的模块函数在一维numpy数组中找到局部最大值/最小值?显然,最简单的方法是看一下最近的邻居,但我希望有一个被接受的解决方案,它是发行版的一部分。 问题答案: 如果你要查找一维数组中所有小于其邻居的条目,则可以尝试 你还可以在使用此步骤之前使数组平滑。 我认为没有专用的功能。

  • 问题内容: 假设我在NumPy中有一个包含连续微分函数求值的数组,我想找到局部最小值。没有噪音,因此每个点的值都低于其所有邻居的值都满足我的局部最小值标准。 我有以下列表推导,适用于二维数组,忽略了边界上的潜在最小值: 但是,这很慢。我也想使它适用于任意数量的尺寸。例如,是否有一种简单的方法来获取任何维度数组中的点的所有邻居?还是我完全以错误的方式来解决这个问题?我应该改用吗? 问题答案: 可以使

  • 我有一个熊猫数据框,有两列,一列是温度,另一列是时间。 我想做第三和第四列,叫做最小和最大。这些列中的每一个都将填充nan's,除非有一个局部min或max,那么它将具有该极值的值。 这里是一个数据的样本,本质上我试图识别图中所有的峰值和低点。 有没有内置的熊猫工具可以做到这一点?

  • 问题内容: 我正在尝试创建两种方法,一种找到对象数组中的最小值,另一种找到对象数组中第二个最小值。 我已经这样写了两个 我已经找到了如何找到最小的值,我只需要找到第二个最小的值,我不确定怎么做。 有任何想法吗?谢谢! 问题答案: 像这样的东西:

  • 假设这条线是由熊猫的离散随机数组成的。我怎样才能找到A、B、C、D点? A是第一点和C之间的最高点 C是A和B之间的最低点 B是C和D之间的最高点 您可以使用这些数据来测试:[1, 2, 3, 10, 13, 15, 20, 50, 49, 49, 32, 33, 35, 36, 35, 34, 33, 34, 35, 36, 30, 27, 22, 15, 15, 17, 20, 27, 30,