改进了整数数组子数组求最小值的算法。
今年Spring我为一家IT公司写了实习入学考试。下面描述了一个问题。我不能解决它，所以我需要帮助（目前我要通过新的测试，所以我需要分析我的错误）。我很乐意为你效劳。
输入：一个数组arr，N个整数，arr的N个长度，数字K(K
对于offset的所有容许值，求s_arr（offset）的最小元素
算法复杂度应小于O(n*k)
输出：所有对（偏移量，最小(s_arr（偏移量））
(0, 3)
(1, 3)
(2, 2)
(3, 2)
(4, 1)
(5, 1)
(6, 1)
s_arr(0) = {4, 5, 3} -> min = 3
s_arr(1) = {5, 3, 3} -> min = 3
s_arr(2) = {3, 3, 2} -> min = 2
s_arr(3) = {3, 2, 7} -> min = 2
s_arr(4) = {2, 7, 1} -> min = 1
s_arr(5) = {7, 1, 5} -> min = 1
s_arr(6) = {1, 5, 9} -> min = 1
我的微不足道的解决方案：
for(int i = 0; i < N - K; i++)
int min = arr[i];
for(int j = 0; j < K; j++)
if (min > arr[i+j])
min = arr[i+j];
print("(" + i + "," + min + ")")
显然，复杂度为O(n*k)。应该做些什么来降低这种算法的复杂度呢？
共有1个答案
您可以使用众所周知的滑动窗口最小算法来实现O(N)复杂度。
这里有一篇关于它的文章:http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
-
我想从数组的一部分找到最大值和最小值。我知道我可以通过复制数组将所需的数组部分复制到另一个数组中，但只是想知道是否可以不复制数组，因为我必须为不同的子数组进行循环 例如： 现在我想从1到4找到子数组的最小/最大值（如果可能，不复制子数组）
-
这是一个非常基本的算法（不能再简单了），但我被难住了。我们有一个元素数组，我们必须确定最小值和最大值。 通常的方法是遍历数组，找出最小值和最大值，即2n比较。 稍微有效的方法是首先对数组的连续元素进行比较，以确定任意两个元素的最大值和最小值(N/2比较）。我们现在有n/2 min和n/2 max元素。现在我们可以在n/2+n/2+n/2（前一步）=3/2*n或1.5n中得到最终的max和min 那
-
我正在尝试以下练习来提高我的在线技能，我遇到了以下问题。 这是一个演示任务。 编写一个函数：class Solution{public int Solutions（int[]A）；}，给定一个包含N个整数的数组A，返回A中没有出现的最小正整数（大于0）。 举个例子， 给定 A = [1， 3， 6， 4， 1， 2]，函数应返回 5。给定 A = [1， 2， 3]，函数应返回 4。给定 A =
-
如何计算下面代码中的整数值： 我想实现如果0是超过1所以将打印假如果1是超过0将打印真
-
编写一个函数: 函数解($ A)； 给定一个包含 N 个整数的数组 A，返回 A 中未出现的最小正整数（大于 0）。 例如，给定A = [1，3，6，4，1，2]，函数应该返回5。 再比如，给定A = [1，2，3]，函数应该返回4。 给定A =[1，3]，该函数应返回1。 假设： N是[1…100,000]范围内的整数；数组A的每个元素都是[−1,000,000…1,000,000]范围内的整数