计算数组中的交替数字

本文关键字：数字 数组 计算 | 更新日期: 2024-11-08 16:56:56

给定一个整数数组...

var numbers = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };

我需要确定一个向上然后向下或向下然后向上交替的最大数字序列。

不确定解决这个问题的最佳方法，这个过程 伪明智 我觉得很简单，但它的具体化代码正在逃避我。

关键是我们正在寻找最大序列的事实，所以虽然上面的数字可以用多种方式解释，比如七个向上-向下向上和七个向下向上-向下的序列，但重要的事实是从第一个数字开始，有一个向下向上向下的序列长度为 14。

我也不应该计算第一项，121 是长度为 3 的序列，有人可能会争辩说序列直到第二位数字才开始，但不要分裂头发。

计算数组中的交替数字

这似乎有效，它假设数字的长度大于 4（无论如何这种情况应该是微不足道的）：

var numbers = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };
int count = 2, max = 0;
for (int i = 1; i < numbers.Length - 1; i++)
{
    if ((numbers[i - 1] < numbers[i] && numbers[i + 1] < numbers[i]) ||
                    (numbers[i - 1] > numbers[i] && numbers[i + 1] > numbers[i]))
    {
        count++;
        max = Math.Max(count, max);
    }
    else if ((numbers[i - 1] < numbers[i]) || (numbers[i - 1] > numbers[i])
                || ((numbers[i] < numbers[i + 1]) || (numbers[i] > numbers[i + 1])))
    {
        max = Math.Max(max, 2);
        count = 2;
    }
}
Console.WriteLine(max); // 14

这是我的想法

  • 首先，你需要知道你是从高处开始还是从低处开始。 例如：1-2-1或2-1-2。您甚至可能没有交替配对。
  • 然后，您之后考虑每个数字，看看它是否属于序列，同时考虑当前方向。
  • 每次序列中断时，您都需要通过检查方向重新开始。

我不确定是否有可能在你已经看到的数字中，选择一个不同的起始号码可能会产生更长的序列。也许有一个定理表明这是不可能的;也许这是显而易见的，我想多了。但我认为这是不可能的，因为序列被破坏的原因是因为你有两个高点或两个低点，没有办法解决这个问题。

我假设了以下情况

  • {} - 无元素，返回 0
  • {1} - 单个元素，返回 0
  • {1, 1, 1} - 无交替序列，返回 0

对输入没有超出 C# 预期的限制。它可能会被压缩。不确定是否有办法在不明确跟踪方向的情况下捕获方向变化逻辑。

static int max_alternate(int[] numbers)
{
  int maxCount = 0;
  int count = 0;
  int dir = 0; // whether we're going up or down
  for (int j = 1; j < numbers.Length; j++)
  {
      // don't know direction yet
      if (dir == 0)
      {
          if (numbers[j] > numbers[j-1])
          {
              count += 2; // include first number
              dir = 1; // start low, up to high
          }
          else if (numbers[j] < numbers[j-1])
          {
              count += 2;
              dir = -1; // start high, down to low
          }
      }
      else
      {
          if (dir == -1 && numbers[j] > numbers[j-1])
          {
              count += 1;
              dir = 1; // up to high
          }
          else if (dir == 1 && numbers[j] < numbers[j-1])
          {
              count += 1;
              dir = -1; // down to low
          }
          else 
          {
              // sequence broken
              if (count > maxCount)
              {
                  maxCount = count;
              }
              count = 0;
              dir = 0;
          }
      }
  }
  // final check after loop is done
  if (count > maxCount)
  {
      maxCount = count;
  }
  return maxCount;
}

还有一些测试用例，其结果基于我对问题的理解和一些假设。

static void Main(string[] args)
{
    int[] nums = { 1};            // base case == 0
    int[] nums2 = { 2, 1 };       // even case == 2
    int[] nums3 = { 1, 2, 1 };    // odd case == 3
    int[] nums4 = { 2, 1, 2 };    // flipped starting == 3
    int[] nums5 = { 2, 1, 2, 2, 1, 2, 1 }; // broken seqeuence == 4
    int[] nums6 = { 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1 }; // long sequence == 14
    Console.WriteLine(max_alternate(nums));
    Console.WriteLine(max_alternate(nums2));
    Console.WriteLine(max_alternate(nums3));
    Console.WriteLine(max_alternate(nums4));
    Console.WriteLine(max_alternate(nums5));
    Console.WriteLine(max_alternate(nums6));
    Console.ReadLine();
}
我现在

不是来自带有编译器的PC，所以我只是尝试一下：

int max = 0;
int aux =0;
for(int i = 2 ; i < length; ++i)
{
    if (!((numbers[i - 2] > numbers[i - 1] && numbers[i - 1] < numbers[i]) ||
           numbers[i - 2] < numbers[i - 1] && numbers[i - 1] > numbers[i]))
    {
        aux = i - 2;
    }
    max = Math.Max(i - aux,max);
}
if (max > 0 && aux >0)
    ++max;

注意：应该适用于至少 3 个元素的序列。

可能有很多

方法可以解决这个问题，但这里有一个选项：

var numbers = new int[] { 7,1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1 };
int maxCount = 0;
for (int j = 0; j+1 < numbers.Length; j++)
{
    int count = 0;
    if (numbers[j] < numbers[j+1])
    {
        count += 2;
        for (int i = j+2; i+1 < numbers.Length; i += 2)
        {
            if (numbers[i] < numbers[i + 1] )
            {
                count += 2;
            }
            else
            {
                break;
            }
        }
    }
    if (maxCount < count)
    {
        maxCount = count;
    }
}
Console.WriteLine(maxCount);
Console.ReadLine();

此解决方案假定您需要一个相同的两个交替数字的序列。 如果这不是必需的，您可以更改第二个if。

现在它被写出来了，它看起来比我脑海中想象的要复杂......也许其他人可以想出更好的解决方案。

假设至少 2 个元素。

int max = 1;
bool expectGreaterThanNext = (numbers[0] > numbers[1]);
int count = 1;
for (var i = 0; i < numbers.Length - 1; i++)
{
    if (numbers[i] == numbers[i + 1] || expectGreaterThanNext && numbers[i] < numbers[i + 1])
    {
        count = 1;
        expectGreaterThanNext = (i != numbers.Length - 1) && !(numbers[i] > numbers[i+1]);
        continue;
    }
    count++;
    expectGreaterThanNext = !expectGreaterThanNext;
    max = Math.Max(count, max);
}

这适用于任何整数，它跟踪低-低-低-高-低，就像你问的那样。

int numbers[] = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };
   int count = 0;
   int updownup = 0;
   int downupdown = 0;
   for(int x = 0;x<=numbers.Length;x++)
   {
      if(x<numbers.Length - 2)
      {
         if(numbers[x]<numbers[x+1])
         {
          if(numbers[x+1]>numbers[x+2])
           {
           downupdown++; 
            }
         }
    }
}
count = 0;
for(x=0;x<=numbers.Length;x++)
{
  if(x<numbers.Length - 2)
  {
    if(numbers[x]>numbers[x+1]
    {
     if(numbers[x+1]<numbers[x+2])
     {
        updownup++;
        }
    }
    }
}
相关文章：