英文:
O(n) solution for a one dimensional closest pair problem?
问题
目前，我正在学习关于最近对算法的知识，并在一本教材中找到了这个问题：
假设你有一个长度为n的排序数组，其中包含一维点（整数），并且这些点有颜色。现在你想要找到两个不同颜色（红色或蓝色）的点的最接近对。你如何在O(n)时间内完成这个任务？因为通常使用分治算法来解决最接近点对问题，所以我想知道是否有人有解决这个问题的方法？
我找到了一个使用双指针的解决方案，但没有分治算法的解决方案。
英文:
So, I am currently learning about closest pair algorithms and found this problem in a text book:
Assume you have a sorrted Array of length n that contains one Dimensional points (integers) and are coloured. Now you want to find the closest pair of two points of different colours (either red or blue). How would you do that in O(n)? Since the closest pair of points problem is usually using a divide and conquer algorithm I was wondering whether someone has an idea on how to solve this?
I found a solution using two pointers, but no d&C solution.
答案1
得分: 1
你在评论中提到只有两种颜色，红色和蓝色。
如果我们可以使用分而治之的方法，它将提供O(logn)的解决方案。我认为这是不可能的。然而，有一个相当简单的O(n)解决方案。我们只需要记住最后一个蓝色和红色样本的值/索引。
如果最后一个元素是蓝色（或红色），我们计算它与最后一个红色（或蓝色）元素之间的距离。然后将结果与先前的最小距离进行比较。
注意：如果颜色的数量更多，仍然可以使用堆栈来实现一个简单的O(n)方法。在知道只有两种颜色之前，我最初准备了这样的解决方案。
英文:
You mentioned in a comment that there are only two colours, red and blue.
If we could use a divide-and-conquer approach, it would give a O(logn) solution. I don't think it is possible. However, there is a rather simple O(n) solution. We just have to memorize the value/index of last blue and red samples.
It the last read element is blue (resp. red), we calculate its distance from the last red (resp. blue) element. We then compare the result with the previous minimum distance.
Note: if the number of colours were higher, there is still a simple O(n) approach by using a stack. I originally prepared such a solution, before knowing there are only two colours.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论