时间戳

首页 > 解决方案 > 使用分而治之的 JPEG 图像的大多数元素

algorithm - 使用分而治之的 JPEG 图像的大多数元素

问题描述

你有一个数组 A ，其中有 n 个 JPEG 图像，其中一些是相同的。

您可以检查两个对象是否相等，但不能以任何其他方式比较它们——即您可以检查 A[i] == A[j] 和 A[i] != A[j]，但比较诸如 A[ i] < A[j] 没有意义。

如果严格来说，数组 A 的一半以上元素彼此相等，则称数组 A 具有多数元素。

使用分治法提出 O(n logn ) 算法来确定 A 是否具有多数元素。

..................................................... .........................................

我的解决方案：我通过将图像数组分成两半来解决这个问题，直到数组大小为 1 或 2 。

如果数组的大小为 1，则我们返回该数组中存在的元素，如果它的大小为 2，则我们在数组的元素之间进行比较。如果它们相同，则我们返回该元素，否则它不会返回。

当我们递归地向上移动树时，我们对返回的元素执行相同的操作，直到只有一个返回元素。

我用一个例子来解释会更容易

假设数组是 ABABAABA

STEP 1 我们分成两半

[ABAB][AABA] -> [AB][AB][AA][BA]

现在，[AB] 什么都不返回（因为 A 与 B 不同）

 [AB] returns nothing

 [AA] returns A

 [BA] returns nothing

因此，唯一返回的元素是 A，它是多数元素。现在，我的问题是您会发现上述算法不适用于许多数组，例如 AAAAABBB，但我认为这不起作用只是因为 A 的排序和 B 的数组改组会使问题消失。请告诉我我是否正确？

如果我的算法完全错误，请给出解决方案。

标签： algorithmdivide-and-conquer

解决方案

推荐阅读