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

问题描述

注意-您不能使用收藏夹或地图

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

I have tried this but this is not having complexity 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循环来查找重复数组

Is any one having solution for solving,to find a duplicate array without using Collection or Map and using only single for loop

推荐答案

如果数组中大小为 n 的元素在 0〜n-1 范围内(或 1〜n ).

If the elements in an array with size n are in a range of 0 ~ n-1 ( or 1 ~ n).

我们可以尝试通过对每个 a [i]！= i 放置 a [i] 索引 i 来对数组进行排序，并且如果我们发现索引 i 处已经有 a [i] ，则意味着存在另一个值为 a [i] .

We can try to sort the array by putting a[i] to index i for every a[i] != i, and if we find that there is already an a[i] at index i, it means that there is another element with value 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次交换操作.

Since after every swap, one of the elements will be in the right position, so there will be at most n swap operations.

这篇关于在时间复杂度O(n)和空间复杂度O(1)中查找数组中重复元素的最有效算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！