问题标签 [array-algorithms]

如何查找/存储长度为 n 的数组的所有可能的非空子数组的最大值/最小值？

如果确实查询到段树，我生成了数组的段树和每个可能的子数组，但这效率不高。我如何在 O(n) 中做到这一点？

PS n <= 10 ^7

我有一个洗牌的问题。有很多页面和讨论关于完全洗牌一系列值，比如一摞牌。

我需要的是一个随机播放，它将在远离其起始位置的最多 N 个位置均匀地置换数组元素。

也就是说，如果 N 为 2，则元素 I 最多将被洗牌到从 I-2 到 I+2 的位置（在数组的范围内）。

事实证明，使用一些简单的解决方案会导致元件运动的方向偏差或不均匀的量，这很棘手。

我有一个算法，它基于一个问题，您需要找到到达数组末尾的最小跳转次数。这个问题是在极客中被问到极客的，在我的情况下他们没有线性时间算法算法是在线性时间中，但是对于哪个测试用例，我的算法会失败？.问题的链接

链接：- http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

输入：arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

• 从第一个元素开始，我们知道元素的最大范围是 1，因此我们只能向前移动一步，所以从 1->3

• 现在在第二步中，我们知道元素的范围是 3，因此从该步骤我们计算该范围的最大值，因此我们可以从 3 中选择 5、8、9，并且该范围内的最大值为 9

• 所以首先移动到 9，即 1->3->9，然后从 9 移动到数组的末尾，因为我们知道九步足以到达末尾。

• 极端情况是，如果我们在末尾检测到零，我们什么也不做，因为我们已经到达了末尾。但是如果在开始时检测到零，或者在 0 是该范围内向前移动的最大元素的范围内检测到零，我们将返回a -1，因为我们无法继续前进，请告诉我此算法中是否存在错误。

对于这个程序，我有一个用户使用该private static void add()方法将元素输入到一个 5 空间数组中。添加这些元素后，用户可以使用该private static void delete()方法允许他们输入他们希望删除的数组中存在的数字。输入要删除的数字时，程序运行良好，除非我尝试删除currentSize数组的最后一个数字。例如，如果我有一个包含以下索引和值的数组：

数组的currentSize当前值为 4。如果我尝试删除索引 3 中的值 4，程序将不会删除值 4。如果我在尝试删除值 4 后尝试删除值 3、2 或 1，这些值将不会删除任何一个。另一方面，如果我想首先删除值 4 以下的任何值，即值 1、2 和 3，则程序可以正常工作，直到我尝试删除索引 0 中的值 4。如果我尝试删除值 4此时，没有任何内容被删除。如果我尝试添加一个值，比如 1，在尝试删除值 4 之后，值 4 将替换为值 1。如果我尝试在索引 0 处删除值 4 两次，然后尝试添加一个新值，我会得到一个IndexOutOfBoundsException: -1. 我相信这与currentSize--递减有关，因为它不应该出现在private static void delete()方法。如果有人对此有解决方案，将不胜感激，谢谢。该程序发布在下面。我已经评论了private static void delete()给我问题的方法部分。这是我得到的堆栈跟踪：

有人可以提供 NlogN 复杂高效的程序来计算 i 左侧小于 A[i] 的值吗？

我知道如何在 n 方中做事。如果可能的话提供链接。

0/1 背包的概念 - 使用给定的重量填充 W 重量的背包。目标是最大化利润。Ans-Problem 可以通过采用特定权重或不采用特定权重来解决，具体取决于哪个获得最大利润。通过这种方式可以计算出最优解。

现在，最小硬币找零问题 - 找到最小号码。硬币做出特定的改变。Ans-根据我的想法，可以通过取或不取特定硬币来解决，这取决于哪一个给出的最小值。硬币。只有 0/1 背包中的最大值条件会被反转。

但在实际的解决方案中是这样 的——在 geeksforgeeks 上给出的答案

现在，最小硬币变化问题的变化 - 我们必须为特定变化找到所有可能的硬币组合，遵循背包的概念。我不明白为什么？

就像这里完成了-

请帮助我理解为什么我的背包思维过程不适用于最低限度。硬币做出特定的改变。我哪里错了？还是我对 0/1 背包的概念有误，如果是，请解释两者。

输出：1 1 1 1 0 0 2 2

我能够获得所需的输出，但我不确定这是否是解决我的问题的最佳方法？

我正在观看有关合并排序的 Coursera Princeton 算法讲座，我了解所有分析，除了合并最多 6 n log n 数组访问。

为什么是6？

以下 - 插入排序、选择排序、合并排序、基数排序的复杂性并解释哪一种是最好的排序算法，为什么？

假设有一个整数数组arr[0..n-1]。找到一个子序列sub[i..j]（i > 0 和 j < n - 1），使得数组的其余部分具有最小的平均值。

例子：

移除{7,8}，数组变为{5, 1, 2}平均为 2.67（尽可能小）。

我认为这是对最长增加子序列的修改，但无法弄清楚。

谢谢，