Найти последовательности любого диапазона

Question

Учитывая массив чисел, распечатайте каждый доступный диапазон. Например: Array: 9, 3, 5, 7, 4, 8, 1 Выход: 1, 3-5, 7-9 Примечание: Пожалуйста, выполните эту проблему, не используя дополнительный массив.

Как я могу продолжить? *

#include<stdio.h> 
int main() 
{ 
int a[]={9,8,8,7,6,5,14}; 
int n= sizeof(a)/sizeof(a[0]); 
int i,j; 
int temp; 
for(i=0;i<n;i++) 
     { 
       for(j=i+1;j<n;j++) 
       { 
        if(a[i]>a[j]) 
        { 
          temp=a[i]; 
          a[i]=a[j]; 
          a[j]=temp; 
        } 
       } 
     } 
} 

* первый я сортирует в порядке возрастания, я не знаю, что делать дальше? P.S: Я кодирую это в C.

Answer 1

Следующий шаг - идентифицировать последовательности. Попробуйте следующий цикл (не полностью отлажен):

first= next= a[0]; 
for (i=1; i<n; i++) { 
    if (a[i] > next+1) { 
     if (next>first) 
      printf("%d-%d,", first, next); 
     else printf("%d,", first); 
     first= next= a[i]; 
    } 
    else next++; 
} 

Answer 2

Я написал простую, легко читаемую функцию для вас, посмотрите:

void printRange(int sortedArray[], int len) { 
    int i, current, next, printStart, printEnd, startIndex = 0; 
    bool print = false; 

    for (i = 0; i < len; i++) { 
     printStart = sortedArray[startIndex]; 
     printEnd = sortedArray[i]; 

     current = sortedArray[i]; 
     if(i < len -1) { 
      next = sortedArray[i + 1]; 
     } else 
       next = current; 

     if (next - current != 1) { 
      startIndex = i + 1; 
      print = true; 
     } 

     if (print) { 
      if (printStart - printEnd == 0) { 
       printf("%d,", printStart); 
      } else { 
       printf("%d-%d,", printStart, printEnd); 
      } 
      print = false; 
     } 
    } 
} 

Run live.

Примечание для хорошего понимания переменной current , а current и printEnd - это то же самое. Вы можете заменить current на printEnd.

Answer 3

Если вы можете изменить исходный массив, то есть если вы можете отсортировать его, то программа может выглядеть

#include <stdlib.h> 
#include <stdio.h> 

int cmp(const void *lhs, const void *rhs) 
{ 
    int a = *(const int *)lhs; 
    int b = *(const int *)rhs; 

    return (b < a) - (a < b); 
} 

int main() 
{ 
    int a[] = { 9, 8, 8, 7, 6, 5, 14 }; 
    const size_t N = sizeof(a)/sizeof(*a); 

    qsort(a, N, sizeof(int), cmp); 
/*  
    for (size_t i = 0; i < N; i++) printf("%d ", a[i]); 
    printf("\n"); 
*/  
    int *p = a; 
    int *start = a, *end = a; 
    do 
    { 
     if (++p == a + N || *p != *end + 1) 
     { 
      printf("{ %d", *start); 
      start == end ? printf(" }\n") : printf(", %d }\n", *end); 
      start = end = p; 
     } 
     else 
     { 
      end = p; 
     } 
    } while (p != a + N);    
}  

Выход программы

{ 5, 8 } 
{ 8, 9 } 
{ 14 }