c# - 最长升序 C#
问题描述
所以我对 C# 很陌生,并且遇到了一个问题,需要我:
在整数数组中搜索最长的整数升序序列。如果对于所有 i (1 ≤ i ≤ n - 1),如果 xi < xi+1,则元素序列 xi (1 ≤ i ≤ n) 是递增的。数组的大小由用户选择。数组的值是计算机生成的介于 0 和 1000 之间的随机数。程序应打印起始索引和最长升序的长度。
到目前为止,这是我的代码(我只能按升序对数组进行排序):
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace AscendingSequences
{
class AscendingSequences
{
public static void Main(string[] args)
{
Console.WriteLine("Ascending Sequence!");
GenerateNumber();
}
public static void GenerateNumber()
{
int i, j, n, number;
int[] array = new int[100];
int[] array1 = new int[100];
Random random = new Random();
Console.Write("\nInput the number of element to be store in the array: ");
n = Convert.ToInt32(Console.ReadLine());
Console.Write("\nThe {0} array is generating-----\n", n);
for (i = 0; i < n; i++)
{
array[i] = random.Next(1, 20);
Console.Write("\nThe array|{0}| is {1} ", i, array[i]);
}
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(array[j] < array[i])
{
number = array[i];
array[i] = array[j];
array[j] = number;
}
}
}
Console.Write("\nElements of array in sorted ascending order is: ");
for(i=0; i<n;i++)
{
Console.Write("{0} ", array[i]);
}
}
}
}
解决方案
您对数组进行首次排序的方法是错误的,不幸的是,这导致一些人感到困惑。
如果您从订购数组开始,您将丢失这些重要元素的原始位置信息。相反,您应该遍历数组并检查当前元素是否大于前一个元素(升序)。
//start and length are the "current" values and max are the max found
int start = 0, length = 0, maxstart = 0, maxlength = 0;
//loop through array (starting from index 1 to avoid out of bounds)
for (int i = 1; i < array.Length; i++)
{
//check if current sequence is longer than previously recorded
if (length > maxlength)
{
maxstart = start;
maxlength = length;
}
//if previous element <= to current element
if (array[i - 1] <= array[i])
{
//if the current element isn't part of the current sequence, then start a new sequence
if (start + length < i)
{
start = i - 1;
length = 2;
}
else
{
//count the length
length++;
}
}
}
这是一个带有工作代码的 .net 小提琴: https ://dotnetfiddle.net/1GLmEB
编辑:在有关其工作原理的评论中回答您的问题start + length < i
此条件检查当前值是否是序列的一部分。该变量start
是最后/当前找到的序列的开始,并且length
是长度。当此条件返回 true 时,表示它位于最后找到的序列之外,它会重置start
and length
(true = outside, false = inside)的值
因此,让我们通过一些案例来看看为什么会这样:
1 2 3 1 1 2 3 1 1
* > > > e ^
start = 3 (*)
length = 4 (>)
i = 8 (^)
3+4 = e
3+4<8 //true : new sequence
所以最后找到的序列从 3 开始,长度为 4。这意味着该序列将在索引 7 处结束。由于我们当前正在循环中检查索引 8,因此我们可以看到它不是同一序列的一部分。
1 2 3 1 1 2 3 4 1
* > > > > ê
start = 3 (*)
length = 5 (>)
i = 8 (^)
3+4 = e
3+5<8 //false : current sequence
所以最后找到的序列从 3 开始,长度为 5。这意味着该序列将在索引 8 处结束。由于我们当前正在循环中检查索引 8,因此我们可以看到它是同一序列的一部分。
事后看来,如果这个 if 语句被翻转(真 = 内部,假 = 外部),它可能不会那么令人困惑。但是我现在不会更改代码以避免进一步混淆。
推荐阅读
- c# - 在 .NET Framework 4.6 项目上使用 Microsoft.CodeAnalysis.NetAnalyzers
- json - JSON 对象和数组基础知识:什么属于对象,什么不属于?
- gatsby - 如何解决 Gatbsy 并发下载错误
- python - Zeep/requests - 使用自签名证书验证 SSL 连接
- c# - Windows 窗体 PropertyView 不可见文本
- pine-script - 在锯齿形图上调用最高()的问题
- javascript - 在更改密码时更改 Firebase 中的用户信息(Angular)
- android - 在pararell中执行协程并等待所有完成
- python - ValueError:无法在 Python 中同时指定 mapper_raw 和 mapper
- python - 如何将特定类型的文件从一个文件夹中的一组子文件夹复制到另一个文件夹?