在我的算法中，找到每个元素在dista内的最大子数组的大小的缺陷在哪里?

本文关键字：数组 在哪里 缺陷 dista 算法 我的 元素 | 更新日期: 2023-09-27 18:02:28

例如，给定数组A={1,3,2,17,10}，答案是3，因为集合{1,2,3}是最大的集合，因此对于集合中的某些a，集合中的每个元素都是范围[a, a + 4](包括a+4)。

我的算法就像

    int[] toys = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
    Array.Sort(toys);
    int max_together = 0;
    for(int i = 0; i < toys.Length; ++i)
    {
        int plus_four = toys[i] + 4;
        int j = i + 1;
        for(; j < toys.Length && toys[j] <= plus_four; ++j);
        int span = j - i;
        if(span > max_together)
        {
             max_together = span;               
        }
    }

并且大多数测试用例都失败了。

或者我可能读错了https://www.hackerrank.com/challenges/priyanka-and-toys?h_r=next-challenge&h_v=zen…

完整的解是

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    static void Main(String[] args)
    {
        Console.ReadLine(); // N
        int[] toys = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        Array.Sort(toys);
        int max_together = 0;
        for(int i = 0; i < toys.Length; ++i)
        {
            int plus_four = toys[i] + 4;
            int j = i + 1;
            for(; j < toys.Length && toys[j] <= plus_four; ++j);
            int span = j - i;
            if(span > max_together)
            {
                 max_together = span;               
            }
        }
        Console.WriteLine(1 + (toys.Length - max_together));
    }
}

在我的算法中，找到每个元素在dista内的最大子数组的大小的缺陷在哪里?

快速查看，我发现您正试图找到排序数组的最大跨度(即:1,2,3,10,17)，而测试用例希望您找到给定数组的最大跨度(即。1、3、2、17、10)，排序前的那个

如果您购买1个重量为w1的玩具，您将免费获得重量在[w1,w1+4]之间的所有玩具。这个问题要求你找到你需要购买的最小玩具数量，这样你就能得到输入中的所有玩具。在这个例子中，A={1,3,2,17,10}，答案是3，因为你需要购买玩具1(或2或3)，17和10。

Java代码
int num[] = {1,3,2,17,10};
 Arrays.sort(num);
        int result=1;
        int lastToy=num[0];
        for(int i=1;i<n;i++)
            {
            if(num[i] > lastToy+4)
                {
                result++;
                lastToy= num[i];
            }
        }
相关文章：