arrays - 是否有比天真更好的解决方案来查找数组顺序中的错误？

Question

我在一次采访中得到了以下问题，我得到了一个整数数组，我需要返回数组中不在索引中的整数数，如果数组已排序，则它们会出现在索引中。

例如对于数组 [1,1,3,4,1]，我需要返回 3，因为最后三个整数 (3,4,1) 不在索引中，如果数组已排序，[ 1,1,1,3,4]。
对于 [5,4,3,2,1]，我需要返回 4，([1,2,3,4,5])。

我只提出了一个简单的解决方案，即复制原始数组，然后对其进行排序并比较两个数组，然后计算每个索引中不同元素的数量。
它需要 O(nlogn) 时间和 O(n) 空间。

我觉得我可能遗漏了一些东西，可能有更好的解决方案。有更好的解决方案吗？

Answer 1

天真意味着缺乏智慧/判断力；在压力下获得的简单、优雅的解决方案恰恰相反。

可能有改进的余地，但如果它存在，它就不太可能“显而易见”，而且可能并不简单。 (我下面的实验没有证明任何事情，只是我没有看到它；-)

思考
对于要放置的项目，其左侧(在数组中位于它之前)的较大项目的数量必须等于其右侧较小项目的数量。

显然，这可以在不需要第二个阵列的情况下确定。下面的代码具有更好的空间复杂度 O(1) 但时间复杂度更差 O(n^2)。原谅狭窄的风格和递归，但我试图简洁。

using System;
using System.Text;

namespace ConsoleApp2
{
  static class Program
  {
    private static int itemVisits;
    static string PrintArray(int[] arr)
    {
      var sb = new StringBuilder("[");
      foreach (var i in arr)
        sb.AppendFormat("{0}, ", i);
      sb.Length -= 2;// kill last comma and space
      sb.Append("]");
      return sb.ToString();
    }

    static void Test(int[] arr)
    {
      Console.WriteLine($"{PrintArray(arr)}...");
      Console.WriteLine($"  method1: {ItemsOutOfPlace1(arr)} elements out of place, {itemVisits} item visits");
//      Console.WriteLine($"  method2: {ItemsOutOfPlace2(arr)} elements out of place, {itemVisits} item visits");
    }

    static int ItemsOutOfPlace1(int[] arr)
    {
      int countOutOfPlace = 0;
      itemVisits = 0;
      for (int i = 0; i < arr.Length; i++)
        countOutOfPlace += NeedToMove(arr[i], i) != 0 ? 1 : 0;
      return countOutOfPlace;

//  In place functions follow...
      int NeedToMove(int val, int i) { return CountRightLessThan(val, i + 1) - CountLeftGreaterThan(val, i - 1); }

      int CountRightLessThan(int val, int i)
      {
        if (i >= arr.Length) return 0;
        itemVisits++;
        return (arr[i] < val ? 1 : 0) + CountRightLessThan(val, i + 1);
      }

      int CountLeftGreaterThan(int val, int i)
      {
        if (i < 0) return 0;
        itemVisits++;
        return (arr[i] > val ? 1 : 0) + CountLeftGreaterThan(val, i - 1);
      }
    }

    static void Main(string[] args)
    {
      Test(new []{ 1,1,3,4,1 });
      Test(new []{ 5, 4, 3, 2, 1 });
      Test(new []{ 2,3,4,1,6,7,8,9,5 });
      Test(new []{ 30,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,1 });

      Console.ReadKey();
    }
  }
}

生产

[1, 1, 3, 4, 1]...
  method1: 3 elements out of place, 20 item visits
[5, 4, 3, 2, 1]...
  method1: 4 elements out of place, 20 item visits
[2, 3, 4, 1, 6, 7, 8, 9, 5]...
  method1: 9 elements out of place, 72 item visits
[30, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 1]...
  method1: 2 elements out of place, 870 item visits

严格来说是 T(n(n-1))。我试图对此进行改进(您可能已经发现注释掉的对 ItemsOutOfPlace2() 的引用)但没有排序，仅实现了最佳情况时间 O(nlog(n)) 并且需要返回 O(n) 空间以及更多不那么优雅的代码。

结论

如果没有正式的分析，就没有简单/明显的方法来改善空间和时间复杂度。 (如果有，它可能必须增加代码复杂性)。

非正式分析表明，每个项目都必须被“定位”，如果你能以比 O(nlogn) 时间更便宜的方式来处理任意数据，你就会发现一个新的最坏情况优于 O(nlogn)排序算法。

我的“天真”解决方案仅在空间和时间成本上有所改进。除非确实负担不起阵列分配，否则您的选择更可取。此外，您可以使用任何排序算法，因此如果您碰巧知道数据通常几乎已排序，则可以使用利用此功能的排序，例如 Timsort 或 Block 排序，此类输入的时间复杂度接近 O(n)。

好问题