问题标签 [array-algorithms]

我想对数组进行排序并按排序顺序查找每个元素的索引。因此，例如，如果我在数组上运行它：

我会得到：

有没有一种简单的方法可以在 Java 中做到这一点？

给定一个 n*n 元素的二维数组：

• 所有行都已排序
• 所有列都已排序

例如：

将其转换为一维排序数组。有没有比O(nlog(n)).

Constraints :

1. O(1) space
2. O(n) Time

It is not a homework question just a interesting question I came across.

Here are some solutions I could think of but nothing that does it in given constraints.

Method 1

*With O(n) memory *

• Divide the array in two parts recursively. ( keep dividing till the size <=2 for each sub problem )
• Sort each sub problem with array first and numbers at end.
• Merge the sub problem arrays

Method 2

In O(n log n) time

• Sort the array based Lexicographical order it becomes 1234abcd
• Reverse both halves of array 4321dcba
• Reverse the whole string abcd1234

Method 3

If range of numbers was defined

Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 << a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.

Method 4 We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.

Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.

Generic Problem here refers to:

Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 < x2 <.... < xn and y1y2...yn are integers . y1 < y2 <.... < yn Arrange the output as x1x2...xny1y2...yn

Any suggestions ?

给定的是成对的整数(a1,b1),...,(an,bn)。如果和，对i由对“支配” 。什么是快速确定不受任何其他对支配的对列表的算法？jai < ajbi < bj

我们可以检查所有对，并且对于每一对，通过再次遍历所有对来检查它是否被任何其他对支配。这个算法是有序的n^2。是否有顺序算法n或n log n？

我正在尝试查找具有以下 2 个属性的列表的子列表（至少有一个正整数） 1. 它的元素之和为正 2. 它具有所有其他子列表的最大长度和正和

我只对那个列表的长度感兴趣。Kadane 的算法在 O(n) 时间内找到总和最大的子列表。有没有一种算法可以在 O(n) 中做同样的事情？我找到了一个解决方案，但它确实计算了所有子列表，当然非常慢......

感谢您的时间

考虑一个包含 N 个整数的数组。找到最长的连续子数组，使其元素的平均值大于（或等于）给定数 k。

显而易见的答案具有 O(n^2) 复杂度。我们能做得更好吗？

我无法理解以下内容：
我们有 String ABRACADABRA。我们以分组为例： S分组：

S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...> where<>表示一个数组，S[i] 表示Sposition 中的字符i。

我期待这一点，S0=<S[0]S[4]S[8]S[11]>但根据我阅读的书中的“解决方案”，它S0=[ABR][ACA][DAB][RA]本质上不是S[0]S[3]S[6]S[9].
那么我在公式中读错了S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...>什么？

如果重要的话，它来自我读过的关于后缀数组的一章。我只有公式有问题

在这个程序中，我只想对ArrayList words. 到目前为止，我使用了Collections.sort它，它已按字母顺序将所有行放在文本文件中。但是，我想为这个程序实现一个二进制搜索算法，但是，我认为如果不对数据进行排序（例如合并排序、冒泡排序）就不可能这样做。我可能错了，但这就是我来这里寻求指导和知识的原因。

其次，当我创建一个排序方法时，这是 a wordsis a Stringnot an String[]。然后如何使用这种数据类型进行冒泡排序？

所以我对 Java 比较陌生（我目前正在我的学校学习 AP java），我正在尝试开发一种递归算法来解决 n*n 板，我觉得我非常接近，但还没有完全达到。我已经写了所有东西来遍历我的字典以查找我发送的字母是否是单词等。我的算法是让我的数组中的起始字母为 (n,p)，将这些坐标发送到另一个方法去各个方向寻找所有可能的组合。一旦找到以 (n,p) 开头的所有组合，我将递增 p 直到它到达行的末尾，然后我将递增 n 并再次从 0 开始 p。（我只浏览了一半的字母，因为前后组合都是一样的）

我遇到问题的部分是递归序列，因为一旦我越过板上的某个位置，我想标记它以确保在序列的其余部分我永远不会再越过它。它不能完全工作，我想知道是否有人可以告诉我为什么/帮助我编写更好的算法。提前致谢

考虑两个查找函数：

哪个函数的查找成本更低？或者他们是平等的？Lua 如何在内部存储关联数组？