arrays - 有什么办法可以使这段代码更有效率吗？因为我想解决谷歌平台上的挑战，它给了我超过时间限制

Question

这是 problem

Trouble Sort

The basic operation of the standard bubble sort algorithm is to examine a pair of adjacent numbers, and reverse that pair if the left number is larger than the right number. But our algorithm examines a group of three adjacent numbers, and if the leftmost number is larger than the rightmost number, it reverses that entire group.

Because our algorithm is a "triplet bubble sort", we have named it Trouble Sort for short.

For example, for L = 5 6 6 4 3, Trouble Sort would proceed as follows:

• First pass:
  • inspect 5 6 6, do nothing: 5 6 6 4 3
  • inspect 6 6 4, see that 6 > 4, reverse the triplet: 5 4 6 6 3
  • inspect 6 6 3, see that 6 > 3, reverse the triplet: 5 4 3 6 6
• Second pass:
  • inspect 5 4 3, see that 5 > 3, reverse the triplet: 3 4 5 6 6
  • inspect 4 5 6, do nothing: 3 4 5 6 6
  • inspect 5 6 6, do nothing: 3 4 5 6 6
• Then the third pass inspects the three triplets and does nothing, so the algorithm terminates.

It is possible that Trouble Sort does not correctly sort the list! Consider the list 8 9 7, for example.

Given a list of N integers, determine whether Trouble Sort will successfully sort the list into non-decreasing order. If it will not, find the index (counting starting from 0) of the first sorting error after the algorithm has finished: that is, the first value that is larger than the value that comes directly after it when the algorithm is done.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines: one line with an integer N, the number of values in the list, and then another line with N integers V_i, the list of values.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is OK if Trouble Sort correctly sorts the list, or the index (counting starting from 0) of the first sorting error, as described above.

Sample

Input      | Output
-----------+-------------
2          |
5          |
5 6 8 4 3  |  Case #1: OK
3          |
8 9 7      |  Case #2: 1

Sample Case #1 is similar to the first one described in the problem statement. Trouble Sort correctly sorts this list, so the answer is OK.

Sample Case #2 is the second one described in the problem statement. Trouble Sort does not correctly sort this list, since it terminates with the list 7 9 8. The 9 is the first value in the list that is larger than the next value, so the index of the first sorting error is 1.

测试集1与冒泡排序一样，问题排序具有 O(N2) 时间复杂度；下面解释证明。对于测试集 1 N ≤ 100，我们可以运行故障排序直到完成并简单地遍历结果列表以找到第一个排序错误，如果有的话(即大于列表中它后面的值的值).

测试集2对于 N ≤ 105，运行 O(N2) 次故障排序太慢。

相反，让我们分解一下 Trouble Sort 在每个步骤中所做的事情。让我们考虑一个包含 6 个元素的输入列表。问题排序在每次通过数组时进行以下比较:

元素 0 ↔ 元素 2元素 1 ↔ 元素 3元素 2 ↔ 元素 4元素 3 ↔ 元素 5不管列表的长度如何，这张表说明了问题排序的根本缺陷:偶数索引元素与其他偶数索引元素进行比较，奇数索引元素与其他奇数索引元素进行比较，但偶数索引和奇数索引元素永远不会相互比较!这意味着问题排序只是在偶数索引元素和奇数索引元素上分别运行的冒泡排序，将它们交织到输出列表中。仅当交错两个子列表(偶数索引列表和奇数索引列表)恰好产生另一个排序列表时，故障排序才是正确的。由于有 O(N) 个偶数索引和 O(N) 个奇数索引元素，并且由于冒泡排序是 O(N2)，因此问题排序也是 O(N2)。

为了解决测试集 2，我们可以在上面描述的两个子列表上独立运行我们最喜欢的 O(N log N) 排序算法，交错排序的子列表，然后找到第一个排序错误，如我们测试集 1 的解决方案。

我已经尝试过的是尽量减少嵌套 for 的使用以降低时间复杂度，除了检查所有位置并返回索引之外，我找不到另一种方法来检查我的数组是否已排序排序算法不起作用

这是完整的代码，我正确地实现了它，因为当给出第一个测试用例时它给出了结果，但是它超过了 20 秒的时间，如果有其他解决方案，我想知道。

import 'dart:io';
import 'dart:math' as math;
import 'dart:async';
import 'dart:convert';

Stream<String> readLine() => stdin
    .transform(utf8.decoder)
    .transform(const LineSplitter());

main() {
  String stringCase;
  //List<String> results =[];

  int numberOfCases = int.parse(stdin.readLineSync());
  stdout.flush();
  // we read the input as google wants,
  BytesBuilder builder = new BytesBuilder();
  for (int i = 1; i <= numberOfCases; i++) {
      int size = int.parse(stdin.readLineSync());
      List<int> lint = new List(size);
      for (int j = 0; j < size; j++) {
        int char = stdin.readByteSync();
        while (char >= 48 && char <= 57) {
          builder.addByte(char);
          char = stdin.readByteSync();
        }
        lint[j] = int.parse(String.fromCharCodes(builder.takeBytes()));
      }
      //print(lint);
      if(lint.length > 1 && lint.length <= math.pow(10, 9)){
   print("Case #${i}: ${separateArray(lint)}");
      stdout.flush();
  }

  }

  return 0;
}

separateArray(array){

  List<int> odds = new List((array.length / 2).floor());
  List<int> evens= new List(array.length - odds.length);

  int m, n;
  m = 0;
  n = 0;
  for(var i = 0; i<array.length; i++){
    if(i%2==0){
     evens[n] = array[i];
     n++;
    }
    if(i%2!=0){
      odds[m] = array[i];
      m++;
    }
  }
  evens = evens..sort();
  odds = odds..sort();
  var j=0,k=0;
  for(var i=0; i<array.length-1;i++){
    if(i%2==0){
      if (evens[j] > odds[k]) {
          return i;
      }
      j++;
    }else{
      if (odds[k] > evens[j]) {
        return i;
      }
      k++; 
    }
  }
  return "OK";
}

Idk 如果你们看到任何我没有看到的东西。我会很感激一些帮助

Answer 1

假设有 10000 个值的输入，其中 Trouble Sort 将在索引 3 处给出第一个错误。那么对整个 10000 个值的数组(5000 的两倍)进行排序真的不值得付出努力。确定奇数和偶数系列中的最小值和第二最小值就足够了。

针对这种情况的常见补救措施是使用优先级队列，例如最小堆。

因此，您可以将奇数和偶数系列组织到最小堆中，然后开始从中弹出值，直到您检测到错误的顺序。

您甚至可以内联(交织)实现这两个堆，而无需将奇数/偶数值复制到新的专用数组中。

Building a heap当以自下而上的顺序完成并筛选每个子根时，需要 O(n)。

在最坏的情况下，问题排序结果对数组进行了正确排序，您将花费 O(nlogn) 时间从两个堆中弹出所有值，这与您的时间复杂度相匹配已经有了。