java - 重复的数组元素

Question

我试图在数组中找到 n 个重复的元素。如果我的数组大小是 2N，假设有 N+1 个唯一元素，并且其中一个元素重复了 N 次。

我需要返回重复的元素。

Example 1:

Input: [1,2,3,3]
Output: 3

这是我的代码。我想要一个最优解，如果可能的话，在恒定的时间内找到结果。

    public class FindRepeatedElement {
    public static void main(String[] args) {
        int[] inputArr = new int[] {1,2,3,3};
        findRepeatedElement(inputArr);


    }


    public static void findRepeatedElement(int[] inputArr) {
        int i = 0;
        int j = 0;
        int count = 1;
        int match = 0;
        while(i < inputArr.length && j < inputArr.length - 1) {
            if(inputArr[i] == inputArr[j]) {
                count = count + 1;
                if(count == 3) {
                    match = inputArr[i];
                    System.out.println("MATCH " +match);
                } else {
                    j++;
                }
            }else {
                j++;        
            }

        }
     i++;
    }
}

我要i继续增加，并继续这个循环。但很明显我在哪里 i在这里，它从 while 循环中出来，并递增 i 。

简而言之，我想要实现的是 if i为0时，循环从j=0开始，并上升至 < array.length 。然后我继续此操作直到 i=1，并递增 j又从0开始。然后转到i=2等等。我不想在这里使用 for 循环，但是有什么办法可以实现这一点吗？

Answer 1

当某个元素在序列中出现非常频繁时，考虑以下事实很有用:如果超过 50% 的元素相等，则该元素必须相邻出现两次。如果我们保证 2N 元素数组中的 N+1 个元素相等(其余元素不同)，那么我们可以只扫描相邻对，并在找到第一个相等的相邻对时停止。这将花费 O(N) 时间和 O(1) 辅助空间。

对于您的问题，我们不能完全保证这一点，因为 2N 元素数组中有重复元素的 N 个副本。但是我们可以推断出相等元素的出现间隔的限制:如果没有相邻的一对出现，那么模式必须看起来像这些情况之一(E 代表相等元素，点代表任何其他元素)元素)。

• E.E.E.E.E.E.E.间隔均匀，两个分开。
• .E.E.E.E.E.E.E间隔均匀，两个分开。
• E.E.E..E.E.E.E间隔均匀，两根相距，但一间隔为3。

我们几乎可以保证一定有一对相隔两次的出现，但有一种特殊情况，即 E..E 的 N = 2 。在这种情况下，它们的间隔为三。因此，有一个简单的算法，需要 O(N) 时间和 O(1) 辅助空间:对于每个索引 i ，比较arr[i]与 arr[i+1] , arr[i+2]和arr[i+3] 。如果它等于其中任何一个，那么您就找到了重复元素。

一个稍微聪明的算法是比较 arr[0] == arr[2] (涵盖第一个特殊情况)，然后 arr[1] == arr[3] (对于第二种特殊情况)，则 arr[0] == arr[arr.length - 1] (对于第三种特殊情况，包括 E..E )。如果这些都找不到重复元素，则对于每个 i我们只需要测试 arr[i] == arr[i+1]找到它。