java - 在时间复杂度为 O(n) 和空间复杂度为 O(1) 的数组中查找重复元素的最有效算法是什么？

Question

注意- 您不能使用 Collection 或 Map

我试过了，但这没有复杂度 O(n)

class RepeatElement  
{ 
    void printRepeating(int arr[], int size)  
    { 
        int i, j; 
        System.out.println("Repeated Elements are :"); 
        for (i = 0; i < size; i++)  
        { 
            for (j = i + 1; j < size; j++)  
            { 
                if (arr[i] == arr[j])  
                    System.out.print(arr[i] + " "); 
            } 
        } 
    } 

    public static void main(String[] args)  
    { 
        RepeatElement repeat = new RepeatElement(); 
        int arr[] = {4, 2, 4, 5, 2, 3, 1}; 
        int arr_size = arr.length; 
        repeat.printRepeating(arr, arr_size); 
    } 
} 

有没有人有解决方案，在不使用 Collection 或 Map 并且只使用单个 for 循环的情况下找到重复的数组

Answer 1

如果数组中的元素大小为 n范围为 0 ~ n-1 (或 1 ~ n)。

我们可以尝试通过放置 a[i] 来对数组进行排序。到索引 i每 a[i] != i ，如果我们发现已经有 a[i]在索引 i ，这意味着还有另一个值为 a[i] 的元素.

for (int i = 0; i < a.length; i++){
  while (a[i] != i) {
    if (a[i] == a[a[i]]) {
      System.out.print(a[i]);
      break;
    } else {
      int temp = a[i];  // Putting a[i] to index i by swapping them
      a[i] = a[a[i]];
      a[temp] = temp;
    }
  }
}

由于每次交换后，其中一个元素将处于正确位置，因此最多会进行 n 次交换操作。

时间复杂度 O(n)

空间复杂度 O(1)