Форум программистов, компьютерный форум CyberForum.ru

Самая длинная последовательность не повторяющихся элементов в массиве - C++

Восстановить пароль Регистрация
 
newhel
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 5
17.10.2012, 15:51     Самая длинная последовательность не повторяющихся элементов в массиве #1
Помогите!! нужно написать программу,которая выводит на экран самую длинную последовательность не повторяющихся элементов в массиве.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2012, 15:51     Самая длинная последовательность не повторяющихся элементов в массиве
Посмотрите здесь:

Номер столбца, в которой находится самая длинная серия одинаковых элементов. C++
Определить номер столбца матрицы, в котором находиться самая длинная серия одинаковых элементов. C++
Найти номер строки, в которой находится самая длинная последовательность C++
C++ Найти номер строки матрицы, в которой находится самая длинная серия одинаковых элементов
Определить номер столбца, в котором находится самая длинная серия одинаковых элементов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.10.2012, 17:40     Самая длинная последовательность не повторяющихся элементов в массиве #2
Если массив целочисленный и диапазон значений не очень большой, например диапазон между минимумом и максимумом не более 10 000 000, то можно так:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<stdlib.h>
 
void MinMax(int *a, int n, int *min, int *max)
{
   int i;
   for(i = 0, *min = *max = a[i]; i < n; i++)
      if(a[i] < *min) *min = a[i];
      else if(a[i] > *max) *max = a[i];
 
}
 
void Len(int *a, int n, int *i0, int *len)
{
   int i, j, min, max, *count;
   MinMax(a, n, &min, &max);
   count = (int *)calloc(max - min + 1, sizeof(*count));
   if (count == NULL)
      return -1;
   j = max = i = *i0 = 0;
   while(i < n)
   {
       for(; j < n && ++count[a[j] - min] < 2; j++)
          ;
       if (j - i > max)
       {
           max = j - i;
           *i0 = i;
           *len = max;
       }
       for(; i < n && --count[a[i] - min] == 0; i++)
          ;
       i++;
       j++;
   }
   free(count);
}
 
int main( )
{
    int a[] = {1, 2, 3, 4, 2,  1, 0, 2, 1, 1, 1, 2, 3, 4, 5, 6, 7};
    int i, i0, d, size;
    size = sizeof(a) / sizeof(*a);
    Len(a, size, &i0, &d);
    for(i = i0; i < i0 + d; i++)
       printf("%d ", a[i]);
    return 0;
}
newhel
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 5
17.10.2012, 21:05  [ТС]     Самая длинная последовательность не повторяющихся элементов в массиве #3
компилятор ругается! error C2562: Len: функция типа 'void', возвращающая значение
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.10.2012, 21:50     Самая длинная последовательность не повторяющихся элементов в массиве #4
точно, я ее изначально как int прописывал, хотя у меня все и так работало. вот в таком варианте
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<stdlib.h>
 
void MinMax(int *a, int n, int *min, int *max)
{
   int i;
   for(i = 0, *min = *max = a[i]; i < n; i++)
      if(a[i] < *min) *min = a[i];
      else if(a[i] > *max) *max = a[i];
 
}
 
void Len(int *a, int n, int *i0, int *len)
{
   int i, j, min, max, *count;
   MinMax(a, n, &min, &max);
   count = (int *)calloc(max - min + 1, sizeof(*count));
   j = max = i = *i0 = *len = 0;
   if (count == NULL)
      return;
   while(i < n)
   {
       for(; j < n && ++count[a[j] - min] < 2; j++)
          ;
       if (j - i > max)
       {
           max = j - i;
           *i0 = i;
           *len = max;
       }
       for(; i < n && --count[a[i] - min] == 0; i++)
          ;
       i++;
       j++;
   }
   free(count);
}
 
int main( )
{
    int a[] = {1, 2, 3, 4, 2,  1, 0, 2, 1, 1, 1, 2, 3, 4, 5, 6, 7};
    int i, i0, d, size;
    size = sizeof(a) / sizeof(*a);
    Len(a, size, &i0, &d);
    for(i = i0; i < i0 + d; i++)
       printf("%d ", a[i]);
    return 0;
}
newhel
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 5
17.10.2012, 23:26  [ТС]     Самая длинная последовательность не повторяющихся элементов в массиве #5
Спасибо=)

Добавлено через 38 минут
Вы не могли бы рассказать про алгоритм этой программы?
Yandex
Объявления
17.10.2012, 23:26     Самая длинная последовательность не повторяющихся элементов в массиве
Ответ Создать тему
Опции темы

Текущее время: 04:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru