任何2名学生中有年龄差异的儿童的最少人数最多为1。

Question

我需要以下代码的帮助，我正在编写一段代码，以尽量减少聚会中儿童年龄组的数量，即一个组中任何两个孩子的年龄之间的差异应该是0/1。

示例：

儿童总数= 13

儿童年龄=2，2，2，3，3，3，4，4，5，5，6，7

输出

[2,2,2,3,3,3] - group1
[4,4,4,5,5]- group2 
[6,7] - group3

我们不需要打印所有三个数组，组数就足够了，请检查我的代码并告诉我有什么问题

public static void main(String[] args) {
        
    Scanner scan = new Scanner(System.in);
    System.out.println("Enter the number of Kids :");
    int n = scan.nextInt();
    int[] kids = new int[n];
    System.out.println("Enter the ages of kids :");
    for(int i = 0;i<n;i++) {
        kids[i] = scan.nextInt();
    }
    Arrays.sort(kids);
    int groups =0;
    int i =0;
    int k =0;
    int a = 0;
    int b =0;
    for(i=a;i<kids.length-a;i++) {
        for(k=b+1;k<kids.length-b;k++) {
            if(kids[k]-kids[i]!=0 || kids[k]-kids[i]!=1) {
                groups++;
                kids[i] = kids[k];
                a++;
                b++;
            }
                
        }
    }
    System.out.println(groups);
}

Answer 1

您可以在O(n*log(n))时间复杂度中进行排序，在O(n)时间复杂度中进行分组计算。

在循环中维护一个包含当前孩子年龄的变量。如果它超过了任何儿童的年龄增量组，并更新该变量与当前的一个。

看看下面的代码，以便更好地理解。

public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of Kids :");
        int n = scan.nextInt();
        int[] kids = new int[n];
        System.out.println("Enter the ages of kids :");
        for(int i = 0;i<n;i++) {
            kids[i] = scan.nextInt();
        }
        Arrays.sort(kids);
        
        int groups = 1;
        int i = 0;
        int a = kids[i];
        
        for(i=0;i<kids.length;i++) {
            if(kids[i] - a > 1){
                a = kids[i];
                groups = groups + 1;
            }    
        }
        
        System.out.println(groups);
        
        
    }
}

Answer 2

很抱歉使用非常外行的Java，但我只想演示一下逻辑。如果我们只需要数组的计数，那么这可以在排序后的线性时间内完成，因此由于排序的原因，复杂性是O(nlogn)。

public static void main(String[] args) {

    int[] arr = new int[] { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7 };
    int maxArrays = 0;
    Arrays.sort(arr);
    int maxLength = removeDuplicates(arr);

    for (int i = 1; i < maxLength; i++) {
        maxArrays++;
        if (arr[i] - arr[i - 1] == 1)
            i++;// shift
    }

    System.out.println(maxArrays);
}

private static int removeDuplicates(int[] arr) {

    int index = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[index] = arr[i];
            index++;
        }
    }

    return index;
}

Answer 3

如果您只对组数感兴趣，那么您可以在一个线性时间内这样做：

int[] kids= {2,2,2,2,3,3,4,4,5,5,6,7};
Set<Integer> groups=new HashSet<>();

for (int k=0;k<kids.length;k++)
{
    // key is always the even value (2->2, 3->2, 4->4,...)
    int key=kids[k]-kids[k]%2;
    // check on !groups.contains(key) is not necessary as Set.add guarantees no duplicates are added.
    groups.add(key);
}
System.out.println("Number of groups:"+groups.size());

该集合包含在列表中使用年龄键或key+1的子元素存在的偶数年龄。此示例的输出为3。

如果您还想在每个组中保留儿童的年龄，请使用HashMap而不是一组：

HashMap<Integer,List<Integer>> groups;

其中键是偶数年龄(如在集合中)，而值是子年龄的列表。