java - 数组中的重复项 - 可以在 o(n) 中解决吗？

Question

我已经创建了一个代码来检测数组中的重复项，我认为没有比这更快的算法了:

import java.util.HashSet;
import java.util.Set;

    public class Dupe
    {
        public static void main (String[] args)
        {
            int[] myArray = {1, 2, 2, 3, 1, 4, 5, 6, 7, 4};
            Set<Integer> set = new HashSet<>();

            for (int a : myArray)
            {
                if (!set.add(a))
                {
                    System.out.println(a);
                }
            }
        }
    }

它在 O(n) 中。是否也可以在 o(n) 内解决这个问题？

Answer 1

当然没有，因为您必须至少遍历数组一次，而您正在这样做。所以，为了检查你是否有重复，你将在 O(n) ° F(n)(可以是 + 或 *)., 所以你唯一剩下的就是确保你不增加那个速度，所以你需要最小化 F(n) 。检查 Set 中是否有内容是 O(1)，所以您只剩下 O(n)，仅此而已。