программа для объединения элементов в блоки с заданной разницей

Question

Я хочу, чтобы код объединял входной массив в блоки с заданной разницей.

Например:

[20,23,26,28,30,37,45,47,50,60,63,65] -> [[20, 23, 26, 28, 30], [45, 47, 50], [60, 63, 65]] difference of 5.

Примечание. Решение должно иметь O (n) сложность по времени.

Код:

#include<stdio.h>
int main()
{
    int a[100],i,n,diff;
    printf("Enter size of the array: ");
    scanf("%d",&n);
    printf("\nEnter the difference: ");
    scanf("%d",&diff);
    printf("\nEnter an array: ");
    for(i=0;i<n;i++)
      scanf("%d",&a[i]);
    printf("\n[");
    for(i=0;i<n-1;i++)
    {
        if((a[i+1]-a[i]) < diff)
        {
            printf("%d,",a[i]);
            if(!((a[i+2]-a[i+1]) < diff))
              printf("%d",a[i+1]);
        }
        else
          printf("\n"); 
    }
    printf("]");
    return 0;   
}

Answer 1

Это решение будет работать, если массив отсортирован.

private stati c пустые блоки (int [] arr, int n, int diff) {

    int prev = arr[0];
    System.out.print("[[");
    int startIndex=1; // the index after the value of prev is found in the array

    for (int i = 1  ; i < n-1 ; i++ ) {

        if ((Math.abs(prev - arr[i])) <= diff) {
            System.out.print(prev);
            startIndex = i;
            break;
        } else {
            prev = arr[i];
        }
    }

    for (int i = startIndex ; i < n ; i++ ){

        if (Math.abs(prev - arr[i]) <= diff){
            System.out.print("," + arr[i]);
        }
        else if ( i < n-1 && (Math.abs(arr[i+1] - arr[i]) <= diff)){
            System.out.print("],[" + arr[i]);
        }

        prev = arr[i];
    }

    System.out.print("]]");
    System.out.println();
}

Answer 2

import java.util.ArrayList;
import java.util.Scanner;

public class JavaCode {


    public static void main(String[] args) {

        int i, size, diff, previous;

        System.out.println("Enter size of the array: ");

        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();

        ArrayList<Integer> inputArray = new ArrayList<>(size);


        System.out.println("Enter an array: ");
        for (i = 0; i < size; i++) {
            inputArray.add(i, sc.nextInt());
        }
        System.out.println("Enter the difference: ");
        diff = sc.nextInt();

        previous = inputArray.get(0);

        System.out.print("[[" + previous);


        for (i = 1; i < size; i++) {
            if ((inputArray.get(i) - previous) > diff) {
                if (i < size - 1 && (inputArray.get(i + 1) - inputArray.get(i)) < diff)
                    System.out.print("],[" + inputArray.get(i));
            } else {
                System.out.print(", " + inputArray.get(i));
            }
            previous = inputArray.get(i);

        }

        System.out.print("]]");

    }
}

Answer 3

Вот ответ на проблему:

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,n,diff,*a,flag=0;
    printf("Enter size of the array: ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("\nEnter an array: ");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("\nEnter the difference: ");
    scanf("%d",&diff);
    printf("\n[");
    for(i=0;i<n-1;i++)
    {
        if((a[i+1] - a[i]) <= diff)
        {
            if(flag == 0)
            {
                if(i == 0)
                printf("[");
                else
                printf(",[");
            }   
            printf("%d,",a[i]);
            flag = 1;
        }
        if((flag == 1) && ((a[i+1] - a[i]) > diff))
        {
            printf("%d]",a[i]);
            flag = 0;
        }
    }
    if(i == n-1 && flag == 1)
        {
            printf("%d]",a[n-1]);
        }
    printf("]");
return 0;   
}

Answer 4

У вас есть несколько проблем в вашем коде:

• вы никогда не проверяете scanf возвращает 1, в случае неправильного ввода (не int) вы будете использовать неинициализированное значение с неопределенным поведением

• вы не проверяете, что размер входного массива меньше или равен N , в случае, если он больше, вы будете выписать a с неопределенным поведением

• во втором для выражения a [i + 2] доступ из инициализированных значений a и может быть вне a , когда i значений n-2 (последний ход) с неопределенное поведение

• даже если вы не введете предыдущее неопределенное поведение, благодаря входам, которые ваша программа не выдает ожидаемый результат

Решение должно иметь O (n) сложность времени

A l oop подобно для (i = 0; i