问题标签 [array-algorithms]

问题是如何在Java Collection Framework中将数组中的整数堆栈实现为可变大小数组？

我们有一个 n×n 网格，左下角的坐标为 (0,0)，右上角的坐标为 (n,n)。网格中的单元格都有不同的值，我们的目标是找到一个局部峰值，它被定义为一个单元格的值大于它的左、右、上、下邻居（即对角相邻的单元格没有事情）。

问题是，我们只能通过访问该单元格来查看该单元格的值（即，如果不先采取 (i+j) 步从 (0,0) 到达那里，我们就无法检查 (i,j) 的值） ）。我们如何在 O(n) 步中找到局部峰值？

好的，所以我需要设计以下算法（无需代码，只需步骤）：

给定两个集合A，B长度m分别n为，其中每个集合中的数字是不同的，未排序的，并且m<n. 计算两个集合的交集和并集，在任一结果中都没有任何重复值。该算法应该在 O(mlog(n)) 时间内工作。

我很难找出具有如此时间复杂度的算法。最初，我想连接两个未排序的数组，然后对其执行合并排序并删除重复项，但这超出了很多复杂性。

与蛮力 θ(n2) 相比，对数组进行预排序，使算法 θ(nlogn) [排序+查找最小距离]。两个代码都执行相同的工作，但第一个代码显示超出时间限制。我想知道错误是什么。代码中的任何错误？

带有while循环的代码（超出时间限制）

使用 for 循环的代码（效果很好）

设 x 为空数组的大小。如果数组变满，将创建一个长度为 k > x 的新数组。旧数组的内容将被复制到新数组中，新元素也将被存储。

• 在 k 步中创建一个长度为 k 的数组
• 复制一个元素需要固定的时间。

问题：如何选择 k 使得每个插入操作都有摊销的常数时间，并且插入 n 个元素需要 Θ(n)？通过摊销分析证明您的选择会导致每次插入操作的摊销时间恒定。

我的直觉说 k = 2*n 是个好主意，但我不知道如何证明它。我认为我根本不了解摊销分析。有什么建议么？

我刚刚遇到一个问题，我想知道解决这个问题的最佳方法是什么。

我有一个列表列表

假设L的大小是n ，找到在L中出现k次或更多次的所有元素的最佳方法是什么？

例如，如果k = 2，那么我应该得到 [2, 3, 4, 6, 12]。

我需要从给定的字符串数组中找到所有子字符串并将它们分组。

附加条件：

如果字符串 S1 包含字符串 S2，S1 包含 S3，S2 包含 S4 - 它们都应该在一个组中。

例子：

给定数组： Hello, Hello John, Hi, Hi Bob, Hell, Hi all

结果输出：

第 1 组：你好，你好，约翰，地狱

第 2 组：嗨，嗨，鲍勃，大家好

Prepping for an interview. I am trying to practice by solving the following problem: Given an input array of NSNumbers where some of the numbers are duplicated, how can you create another array that only has the unique values in the original array.

I see 2 approaches:

1. Brute-force: Loop through each element in the array, while at a element compare it against the set of numbers in the unique list, if there is a match, don't store it, else add it to the unique list. O(n^2) worst case time?

2. Hash-table based approach: Have a hash-table of length N. Each element of the has-table is NSSet. Every number is mapped to 0,...N-1 using a hashing function. If it is exists in the NSSet corresponding to the "mapped-index", it is not added to "unique array". if not, it is added to set and unique array.

Is this O(N) complexity?

• I looked two ways to implement approach 2 A. NSMutableArray with size of N all initialized to [NSNull null] objects at start. B. NSMutableDictionary where key = hashed mapping integer

Code for each approach is below.

I am noticing that i. Running time of 2A (array approach) is half of that of 2B (Mutabledictionary approach) for the input array of length 403 shown below(0.055ms vs .12ms).
ii. Running time of 1 is ~ 5 times worse 0.25ms. If there are not any duplicates, this discrepancy is even worse.

My Qs are:

1. Is there a better algorithm than 2?
2. Is there a better implementation of algorithm 2?
3. Why is dictionary approach slower? How can I answer this for myself using Instruments profiling. I.e how can I know exact time taken by each step using Instruments?

Code

Hashcode function

1. Brute-Force Approach

2A. Array based hash table

2B. Dictionary based hash table

Input tested ON, 430 elements with some dups and averaged over 40000 iterations

准备面试。尝试使用objective-CIe input = [1,2,2,1,2,3,3,4] output = [1,2,1来解决“从数组中消除连续重复的最快方法”问题,2,3,4]

1. 对于数组内方法：遍历数组中的元素，如果元素 == 前一个元素，则将其删除并重新调整所有其他元素以向下移动。

2. 对于我们可以使用另一个数组的方法。如果 element == 前一个元素，则不要将其添加到新的“唯一数组”中，否则将其添加到唯一数组中。

有没有更好的解决方案？代码如下。可以进行任何优化吗？

使用另一个数组

使用相同的数组

我在 MIT Intro to Algorithms 课上遇到了 Peak Finding Algorithm。我想知道对于一维和二维情况，该算法有哪些实际应用？另外，为什么我们在二维情况下找到列的全局最大值，而不仅仅是列中的峰值？