java - 寻找更好的锯齿形阵列方法

Question

一种 zig-zag 方法，它接受一个数组作为参数并返回一个 zig-zag 数组。

示例:输入 2,6,1,7,9,3 输出9,1,7,2,6,3

返回的数组必须具有替代的最高数字和最低数字。

我能想到这个方法。 //伪代码

public static int [] zig-zag(int arr[])
    {
         arr.sort();
         int returnArr[] = new int[arr.length];
         int begindex = 0, endindex = arr.length -1;
         int idx = 0;
         while(begindex<arr.length/2-1 && endindex>=arr.length/2)
         {
             returnArr[idx++] = arr[endindex];
             returnArr[idx++] = arr[begindex];
             begindex++;endindex--;
         }
         if(arr.length%2 == 1)
         reurnArr[idx] = arr[begindex];
         return returnArr;
     }

该方法的时间复杂度为 O(nlogn)(由于排序)，空间复杂度为 O(n)。 有没有其他方法/算法可以比 O(nlogn) 做得更好？或者 O(nlogn) 且空间复杂度为 O(1) ？

还有一种使用 TC O(n^2) 和 SC O(1) 的方法。但对 O(n^2) 的 TC 不感兴趣。

Answer 1

这是一个可以以时间复杂度 O(nlogn) 完成此任务的算法。 和空间复杂度O(1) 使用链接列表。

该方法适用于具有重复值的列表。

如下:

• 首先，获取您的列表，l ，按降序排列，后半部分相反。 (请注意，您的排序算法必须在链接列表上就地工作，例如 in place merge sort 。)

  例如，使用l = 2, 6, 1, 7, 9, 3 ，这种形式将是 l = 9, 7, 6, 1, 2, 3 。如果您的列表长度为奇数，则前半部分将比后半部分长一个元素。

  执行此操作的一个简单方法是对 l 进行排序降序排列，然后将后半部分的元素反转。

• 接下来，我们创建一些临时变量:

  Node upper = list.head; //Upper half of list pointer
  Node lower = list.get(l.length/2); //Lower half of list pointer
  Node temp = null; //Utility pointer to hold whatever we need
  
  //Let's set up our initial state
  list.get(l.length/2-1) = null; //Disconnect two halves of the list
  temp = upper.next; //Hold upper half minus head
  upper.next = lower; //First element of upper half stitched to bottom half
  
  //Note that lower would need to be at `l.length/2+1` for an odd length list
  //This also applies to list.get in the set up
  //The code could be generalized to both even and odd lenghts by using `Math.ceil`
  // or a similar function to round up instead of Java's default of rounding down
  
  zigZag(upper, lower, temp); //Call to algorithm
  

• 最后是算法:

  public static void zigZag(Node upper, Node lower, Node temp){
      int i = 0; //Controls alternation
      while(temp != null){ //Until temp gets set to null by lower.next or upper.next
          if(i%2==0){ //On even iterations
              upper = temp;
              temp = lower.next;
              lower.next = upper;
          }
          else{ //On odd iterations
              lower = temp;
              temp = upper.next;
              upper.next = lower;
          }
          i++;
      }
  }
  

  或者，这是递归版本:

  public static void zigZag(Node upper, Node lower, Node temp){
      if(temp == null) // temp got set to null by lower.next or upper.next
          return;   // we're done
      upper = temp;
      temp = lower.next;
      lower.next = upper;
      zigZag(lower, upper, temp); //swap upper/lower for next cycle
  }
  

您现在有一个锯齿形链接列表，存储在 l 中.

---

计算时间和空间复杂度:

• 排序:时间 O(nlogn)，空间 O(1)

  • 排序采用原始时间复杂度，并且在就地排序时采用恒定空间

• 逆向:时间 O(n)，空间 O(1)

  • 反转列表的后半部分是 O(n/2) => O(n)

• 临时:时间 O(1)，空间 O(1)

  • 常数数量和大小的简单变量赋值需要常数时间和空间

• 算法:时间 O(n)，空间 O(1)

  • 算法只是简单地改变 next每个节点的指针一次，因此运行时间为 O(n) 。它不会创建任何新变量，因此具有恒定的空间复杂度，O(1)。

  • 递归版本是 tail recursive ，这意味着它只能使用单个堆栈帧，从而使其理论上具有恒定的空间复杂度 O(1)。 (虽然不是在 Java 中，因为它 does not support tail-recursion optimization 。)

将其全部加起来:

如您所见，空间复杂度始终保持不变，使我们的整个程序的空间使用量为 O(1)。

时间复杂度为O(nlogn)+O(n)+O(1)+O(n)，明显以O(nlogn)为主。

由于使用升序排序而额外反转链接列表会减慢程序速度，但不会改变整体时间复杂度。

同样，您可以想出一种排序方式，给出所需的一半降序、一半升序的形式，以节省一些时间，但它也不会改变总体时间复杂度。

加速潜力:

正如 @flkes 在 his answer 中提到的那样，您可以通过降低排序的时间复杂度来降低整个程序的时间复杂度，因为它会产生主导项。

如果您发现一个在 O(n) 时间内就地排序的实现(例如 this linked-list radix sort algorithm 或类似的 bucket sort 算法)，您可以使用常量 O(1 )，空间复杂度，这真的非常好。