arrays - 有没有办法让这段代码更有效率？因为我想在 google 的平台上解决一个挑战，它给了我 Time Limited Exceeded

问题描述

故障排序

标准冒泡排序算法的基本操作是检查一对相邻的数字，如果左边的数字大于右边的数字，则反转该对。但是我们的算法检查一组三个相邻的数字，如果最左边的数字大于最右边的数字，它会反转整个组。

因为我们的算法是“三元组冒泡排序”，所以我们简称为Trouble Sort。

例如，对于 L = 5 6 6 4 3，故障排序将按如下方式进行：

第一关：

检查 5 6 6，什么都不做：5 6 6 4 3

检查 6 6 4，看到 6 > 4，反转三元组：5 4 6 6 3

检查 6 6 3，看到 6 > 3，反转三元组：5 4 3 6 6

第二关：

检查 5 4 3，看到 5 > 3，反转三元组：3 4 5 6 6

检查 4 5 6，什么都不做：3 4 5 6 6

检查 5 6 6，什么都不做：3 4 5 6 6

然后第三遍检查三个三元组并且什么都不做，所以算法终止。

故障排序可能无法正确排序列表！例如，考虑列表 8 9 7。

给定一个包含 N 个整数的列表，确定 Trouble Sort 是否会成功地将列表排序为非降序。如果不是，则查找算法完成后第一个排序错误的索引（从0开始计数）：即大于算法完成时紧随其后的值的第一个值。

输入

输入的第一行给出了测试用例的数量T。T测试用例如下。每个测试用例由两行组成：一行包含整数N，列表中的值的数量，然后另一行包含N个整数V _i，值列表。

输出

对于每个测试用例，输出一行Case #x: y，其中x是测试用例编号（从 1 开始），y如果OKTrouble Sort 正确排序列表，或者是第一个排序错误的索引（从 0 开始计数），如上所述。

样本
Input      | Output
-----------+-------------
2          |
5          |
5 6 8 4 3  |  Case #1: OK
3          |
8 9 7      |  Case #2: 1
示例案例 #1 类似于问题陈述中描述的第一个案例。故障排序正确地排序了这个列表，所以答案是确定的。

示例案例 #2 是问题陈述中描述的第二个案例。Trouble Sort 没有正确排序这个列表，因为它以列表 7 9 8 结束。9 是列表中第一个大于下一个值的值，所以第一个排序错误的索引是 1。

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

测试集 2 运行 O(N2) 故障排序完成对于 N ≤ 105 来说太慢了。

相反，让我们分解一下麻烦排序在每个步骤中所做的事情。让我们考虑一个包含 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 如果你们看到我没有看到的任何东西。我会很感激一些帮助

标签： arraysalgorithmlistsortingdart

arrays - 有没有办法让这段代码更有效率？因为我想在 google 的平台上解决一个挑战，它给了我 Time Limited Exceeded

问题描述

故障排序

输入

输出

样本

解决方案

推荐阅读