求空间复杂度最小的数组中最大整数的和

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）。

正如你所能证明的那样，做得更好是不可能的：占用的内存不能少于输入（或者必须记住所有输入）。由于输入是唯一一个不是常数的东西，所以使用的最大空间是存储输入所需的空间。

Answer 2

解决方案的空间复杂性¹是O(1)。再好不过了。

您的解决方案的时间复杂性是O(N^2)。您可以通过以下几种方式对此进行改进：

• 如果可以修改a，则可以对其进行排序{时间O(NlogN)，空间O(1)}，然后查找/计数最频繁的值{O(N)，O(1)}。总体复杂度为{O(NlogN)，O(1)}。

• 如果无法修改a，请复制它｛O(N)/O(N)｝，然后按上述步骤进行。总体复杂度为{O(NlogN)，O(N)}。

• 如果数字的范围（M）小于数字的数量，则可以使用bucket排序。总体复杂度为{O(N)，O(M)}。

• 使用HashMap可以获得更好的时间复杂性。其总体复杂度将为{O(N)，O(N)}。。。具有明显更大的比例常数。（不幸的是，最糟糕的时间复杂度将是O(NlogN)或O(N^2)，具体取决于哈希图的实现。当所有密钥发生冲突时，就会发生这种情况。这对于Integer密钥和HashMap是不可能的，但对于Long密钥是可能的。）

---

^{1-我指的是空间，此外还有输入数组占用的空间。显然，用于输入数组的空间无法优化。这是既定的}

Answer 3

我理解你的问题。。现在可能有一个解决方案，有n个整数，所有整数都是k[1-n]。然后找到最大重复次数需要O（n）时间。

  public static int maxDuplicateSumSpaceBased(int[] a)
{
  int maxRepCount = 1, tempCount;
  int k=a.length();
  for (int i = 0; i <k; i++)
  {
        a[a[i]%k]+=k;
  }
    int maxRepnumber=0,temp=a[0];
    for (int j = 1; j < k; j++)
    {
      if (temp < a[j])
        {
           temp=a[j];
           maxRepnumber=j;
        }
    }
  }
  return maxRepNum;
}
Then you sum all that number and it take O(n)and O(1) space.