整数数组中包含3个递减值的组数(在O(n ^ 3)时间以下) [英] Number of Groups Consisting of 3 Decreasing values in Integer Array (Below O(n^3) Time)

问题描述

一个递减的三元组定义为一组3个值{a，b，c}，它们的大小从左到右依次减小，使得a> b> c.

A decreasing triple is defined as a set of 3 values {a, b, c} that decrease in magnitude from left to right such that a > b > c.

如何在整数数组中找到这些三元组的数目，其中三元组{i，j，k}的索引不断增加，以使i< & k.

How could one find the number of these triples in an array of integers where the indices of the triple {i, j, k} are increasing such that i < j < k.

例如，考虑以下示例:

{4, 5, 2, 1}
2 decreasing triples: {4, 2, 1} and {5, 2, 1}

{6, 1, 2, 4, 5, 3}
2 decreasing triples: {6, 5, 3} and {6, 4, 3}

{5, 4, 3, 2, 1}
10 decreasing triples:
{5, 4, 3}, {5, 4, 2}, {5, 4, 1}, {5, 3, 2}, {5, 3, 1},
{5, 2, 1}, {4, 3, 2}, {4, 3, 1}, {4, 2, 1}, {3, 2, 1}

O(n ^ 3)解决方案当然是微不足道的；这是Java的实现: *注意:数组很长，但这只是次要的实现细节

The O(n^3) solution is trivial of course; here is an implementation in java: *note: the arrays are of longs, but that is a minor implementation detail

public static long countTriples(long[] measurements)
{
     // O(n^3)
     long count = 0L;

     for(int i = 0; i < measurements.length; i++)
     {
         for(int j = i + 1; j < measurements.length; j++)
         {
             if ( measurements[j] < measurements[i] )
             {

                 for(int k = j + 1; k < measurements.length; k++)
                 {
                     if ( measurements[k] < measurements[j] )
                     {
                         count++;
                     }
                 }
             }
         }
      }   
     return count;
  }
}

我开始使用O(n)方法来定位递减的三元组；它成功地确定了三元组，但是当给定三元组的中间值涉及多个时，我无法正确计数.这就是我现在所拥有的:

I began an O(n) method to locate decreasing triples; it successfully identified triples, but I couldn't get it to count right when the middle value of a given triple was involved in more than one. Here is what I have of that right now:

public static long countTriples(long[] measurements)
{
      ArrayList<Long> greaterOnLeft = new ArrayList<Long>();
      ArrayList<Long> lessOnRight = new ArrayList<Long>();

      HashSet<Long> min = new HashSet<Long>();
      min.add(measurements[measurements.length - 1]);
      HashSet<Long> max = new HashSet<Long>();
      max.add(measurements[0]);

      for(int i = 0; i < measurements.length; i++)
      {
          min.add(measurements[measurements.length - i - 1]);
          max.add(measurements[i]);
          System.out.println("max: " + max + ", min: " + min);
          for(long n : max)
              if (measurements[i] < n) greaterOnLeft.add(measurements[i]);
          for(long n : min)
              if (measurements[measurements.length - i - 1] > n) lessOnRight.add(measurements[measurements.length - i - 1]);
      }

      long count = 0;
      for(long n : greaterOnLeft)
      {
          if(lessOnRight.contains(n)) count++;
      }
      return count;
}

此方法的想法来自HashSet方法，该方法可从本文中查找此类三元组的中间索引:

The idea for this approach came from a HashSet method for locating the middle indices of such tripples from this post:

如何在线性时间中按数组的递增顺序和索引找到3个数字

推荐答案

我相信这可以在O(n ^ 2)时间内解决，而不是那么简单:

I believe this can be solved in O(n^2) time rather trivially:

public static long countTriples(long[] measurements)
{
  // O(n^2)
      long count = 0;
      for(int i = 1; i < measurements.length - 1; i++)
      {
          long right = 0, left = 0;

          for(int j = 0; j < measurements.length; j++)
          {
              if(j < i && measurements[j] > measurements[i]) right++;
              else if (j > i && measurements[j] < measurements[i]) left++;
          }
          count += right * left;
      }
      return count;
}

这篇关于整数数组中包含3个递减值的组数(在O(n ^ 3)时间以下)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！