java - 以最小的空间复杂度查找数组中最大整数的总和

Question

我是编程新手，并试图通过探索来学习。我正在寻找一种解决方案，以找到具有最佳空间复杂度的数组中最大时间重复整数的总和。假设我们有 [1, 2, 3, 3]，结果应该是 6，空间复杂度最小，即 O(n)。

我想出了一个解决方案，但不确定其复杂性。需要一些帮助来理解下面提到的代码是否具有最低的复杂性或者可能更好(当然!)。如果我犯了任何错误，请抱歉，并提前致谢。

public static int maxDuplicateSumSpaceBased(int[] a)
{
  int maxRepCount = 1, tempCount;
  int maxRepNum = a[0];
  int temp = 0;
  for (int i = 0; i < (a.length - 1); i++)
  {
    temp = a[i];
    tempCount = 0;
    for (int j = 1; j < a.length; j++)
    {
      if (temp == a[j])
        tempCount++;
    }
    if (tempCount > maxRepCount)
    {
        maxRepNum = temp;
      maxRepCount = tempCount;
    }
  }
  return maxRepNum * maxRepCount;
}

Answer 1

实际上，输入的空间通常不计入 O 表示法中，因此您的程序的空间复杂度为 O(6)=O(c)=O(1)。 c 是常数。事实上你总是使用 6 个变量。如果使用的空间量取决于输入，则情况有所不同，但这不是您的情况，因为无论您输入的长度如何，您始终使用 6 个变量。

如果您想将输入计算为占用空间(有时确实如此)，假设 n 是输入的长度，您的空间复杂度将为 O(6+n)=O(n)。

不可能做得更好，因为你可以轻松证明: 你占用的内存不能少于输入(或者你必须记住所有输入)。由于输入是唯一不是常量的东西，因此所使用的最大空间就是存储输入 n 所需的空间。