代码之家  ›  专栏  ›  技术社区  ›  CB.

查找int[]中的所有连续数字

  •  5
  • CB.  · 技术社区  · 14 年前

    我想在0到31的随机数的有序整数[8]中找到所有的连续数。连续数字的最小长度必须为3,最大长度为5。

    在这个例子中,最后一个给了我非常真实的问题。

    前任:

    int[] = new int[] { 3,7,14,16,23, 28, 29 ,30 } // no  result (28,29 is length of 2 numbers)
    
    int[] = new int[] { 4,5,6,7,18, 19, 20 ,21 }  // 4,5,6,7 (yes! length of 4!!)
    
    int[] = new int[] { 2.3.4.5.6.7.8.9 } // two results : 2,3,4 and 5,6,7,8,9  
    

    我不想 解决方案 但这只是一个如何解决这个问题的例子,因为我试图使用将军,我真的被卡住了!

    非常感谢你的帮助!

    基督教的

    -这是我开始的代码(不是我厨房里的汤)

    public partial class Test2 : Form
    {
        public Test2()
        {
            InitializeComponent();
        }
    
        private void Test2_Load(object sender, EventArgs e)
        {          
    
             int[] numbers = new[] { 21, 4, 5, 22, 17, 6, 20, 23 };
    
          //  int[] numbers = new[] { 1, 2, 3, 4, 5, 6, 7, 8 };
    
            foreach (Campo r in FindRanges(numbers, 3))
            {
                listBox1.Items.Add(string.Join(", ", r.Select(x => x.ToString()).ToArray()));
            }
    
    
    
        }
    
    
        struct Campo : IEnumerable<int>
        {
            readonly int _start;
            readonly int _count;
    
            public Campo(int start, int count)
            {
                _start = start;
                _count = count;
            }
    
            public int Start
            {
                get { return _start; }
            }
    
            public int Count
            {
                get { return _count; }
            }
    
            public int End
            {
                get { return _start + _count - 1; }
    
            }
    
            public IEnumerator<int> GetEnumerator()
            {
                for (int i = 0; i < _count; ++i)
                {
                    yield return _start + i;
                }
            }
    
            IEnumerator IEnumerable.GetEnumerator()
            {
    
                return this.GetEnumerator();
    
            }
    
    
            public static Campo operator +(Campo x, int y)
            {
                return new Campo(x.Start, x.Count + y);
            }
    
            public Campo removefirst()
            {
                return new Campo(this.Start + 3, this.Count);
            }
    
            public Campo removelast()
            {
                return new Campo(this.Start, this.Count - 1);
            }
        }
    
        static IEnumerable<Campo> FindRanges(IEnumerable<int> source, int minCount)
        {
    
    
            var ordered = source.OrderBy(x => x);
    
            Campo r = default(Campo);
    
            foreach (int value in ordered)
            {
    
                if (r.Count == 0)
                {
                    r = new Campo(value, 1);
                    continue;
                }
    
    
                if (r.Count == 5)
                {
                    r = r.removefirst();
    
                    continue;
                }
    
                if (value == r.End)
                {
                   continue;
                }
    
    
                if ((value == 0 || value == 8 || value == 16 || value == 24) && (r.Count > minCount))
                {
                    continue;
                }
    
                if ((value == 7 || value == 15 || value == 23 || value == 31) && (r.Count == 1))
                {
                    continue;
                }
    
                else if (value == r.End + 1)
                {
                   r += 1;
                }
                else
                {
    
                    if (r.Count >= minCount)
                    {
                        yield return r;
                    }
    
    
                    r = new Campo(value, 1);
                }
            }
    
    
            if (r.Count >= minCount)
            {
                yield return r;
            }
        }
    

    }

    5 回复  |  直到 14 年前
        1
  •  6
  •   Jon Skeet    14 年前

    我建议你举几个例子写在纸上。仔细计算出当你试图用手工解决它们时你直觉上在做什么,然后把它们转换成代码。

    您可能需要记录序列中已找到的值的数量,以及前一个值是什么。。。

        2
  •  2
  •   CB.    14 年前

    很抱歉更新太晚了,但时间很紧。。。。

    这是我的最终解决方案,有所有必要的限制(为我的需要)丝光。 谢谢大家

    static IEnumerable<IEnumerable<int>> Sequences(IEnumerable<int> input, bool ascen = false, int min = 3)
        {
            int ord = ascen == false ? -1 : 1;
    
            input = ord == -1 ? input.OrderByDescending(x => x) : input.OrderBy(x => x);
    
            var seq = new List<List<int>>();
            foreach (var i in input)
            {
                var existing = seq.FirstOrDefault(lst => lst.Last() + ord == i);
                if ((existing == null) || (seq.Last().Count == 5) || i == 7 || i == 15 || i == 23)
    
                    seq.Add(new List<int> { i });
                else
                    existing.Add(i);
            }
            return min <= 1 ? seq : seq.Where(lst => lst.Count >= min);
        }
    
        3
  •  1
  •   Ali Tarhini    14 年前

    伪代码:

    1-按升序对数组排序 2个-

    int count = 0
    for i = 0 to array.length - 2
        if  {array[i + 1] - array[i] = 1 then
            count+=1
        else count=0}
        if { count >= 3 and count <= 5 then found}
    
        4
  •  1
  •   digEmAll    12 年前

    当然,这取决于你的问题是否总是局限于那个约束,我的意思是int[8]数组,0-31,和3-5,但是如果不是,我想你的问题不能用一个简单的算法来解决。

    我是说,假设我们有这个数组:

    int[] = new int[] { 2,3,4,5,6,7,8,9,10,11,12 };
    

    以及你的子集约束,即。 “连续数字集的最小长度必须为3,最大长度为5” .

    从第一个元素到最后一个元素并填充最大可能的连续子集的朴素算法将生成这两个子集:

    [2,3,4,5,6] [7,8,9,10,11]

    在这个解决方案中,12不在任何分区中,但显然还有另一个可行的解决方案(实际上不止一个)包含所有数字,例如:

    [2,3,4,5] [6,7,8,9] [10,11,12]

    因此,您可以有几种可能性:

    1. 第一个解决方案是可以的,您不需要覆盖尽可能多的找到的连续集
    2. 第二种解决方案是可以的,您需要尽可能覆盖找到的连续集
    3. 第二种解决方案是可以的,您需要尽可能多地覆盖一个找到的连续集,并且可能使用尽可能少的子集

    在第一种情况下,你可以像其他回答者指出的那样(嘿,伙计,乔恩·斯凯特回答了你!:P)。
    相反地,在第二和第三种情况下,情况要复杂得多,因为 Knapsack type problem 即一个NP完全问题(第三种情况在我看来特别像 Change-making problem ).

    这是我的两分钱,很明显,我再说一遍,如果你总是有相同的数组大小、范围和子集约束,这个问题就不存在了。

        5
  •  0
  •   pero    14 年前

    1)将给定的数组拆分成连续的数字列表(您说数组已经排序)

    2)添加到列表时,如果列表已经有5个元素添加到新列表

    3)Count列表>2是您的结果