Непрерывная последовательность чисел

С такой постановкой задачи даже хрустеть мозгом не очень хочется.
Расскажи лучше как это применить и, если справишься, мы подумаем...

непрерывную последовательность
1, 6, 10, 4, 7, 8, 3
Решение: 6, 7, 8

Что за? а 10 и 4 не разрывают последовательность?

Надо как бы отсортировать входной массив, но при этом сортировать нельзя. В этом и состоит мозгонасилие задачи.

Короче, сортируем числа, выкидываем дубли, ищем наибольшую возрастующую на единицу последовательность чисел, идущих подряд

гистограмму забульбень

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

int main(int argc, char **argv){
	int i, maxl = 0, imax = -1, curl = 0, icur;
	int *hist;
	long L;
	if(argc == 1) return 1;
	hist = calloc(256, sizeof(int));
	for(i = 1; i < argc; i++){
		if((L = strtol(argv[i], NULL, 10)) > 255) return 2;
		if(L < 0) L *= -1L;
		hist[(int)L]++;
	}
	for(i = 0; i < 256; i++){
		if(hist[i]){
			if(!curl) icur = i;
			curl++;
		}else{
			if(curl > maxl){
				maxl = curl;
				imax = icur;
			}
			curl = 0;
		}
	}
	if(maxl < 2) printf("No sequences!\n");
	else printf("found sequence of %d numbers started from %d\n", maxl, imax);
	return 0;
}

test:

14.09.23 00:07 /tmp
./test 1 3 5 123 32 3 4 1 4 12 13 1
found sequence of 3 numbers started from 3
14.09.23 00:07 /tmp
./test 1 3 5 123 32 3 4 1 4 12 13 1 2 6
found sequence of 6 numbers started from 1
14.09.23 00:07 /tmp
./test 1 3 5 123 32 3 4 1 4 12 13 1 2 6 124 9 125 12 127 1 126 3 122 1 121 2
found sequence of 7 numbers started from 121

а теперь для int64

Для начала предлагаю честно решить задачу с ответом на вопрос, есть ли в исходном массиве два последовательных числа.

Можно наверное сваять ручками дерево хранящее в качестве ключей интервалы а не числа - это будет быстрее ассоциативного массива и (если реализация будет нормальная), да и по памяти зело экономнее.

Оценка сложности для Вашего алгоритма неправильная, поскольку даже на чтение доступ в ассоциативный массив отнюдь не О(1) а скорее логарифмический, уж про запись я вааще молчу;-)

Если диапазон разумный, то можно че то помудрить с битовыми представлениями числа (был такой алгоритм сортировки, забыл название) - наверное его можно адаптировать к этой задаче.

Можно взять по биту на число. Тады по памяти выигрышь в sizeof(тип исходных данных) раз будет по сравнению с исходным массивом, да и потом искать непрерывные последовательности проще.

А набивку массива бит можно распараллелить. На GPGPU!;-)

сортировать исходные данные нельзя.

строится хеш-таблица - или словарь

/0

есть что-либо более другое, более быстрое ?

да. Сделай нормальную сортировку. И скажи, что «это не сортировка, а словарь/хеш».

с битовыми представлениями числа (был такой алгоритм сортировки, забыл название)

корзинки. http://en.wikipedia.org/wiki/Radix_sort

В этом случае я бы использовал списки. Да, дольше, но никакой сортировки зато.1

Можно наверное сваять ручками дерево хранящее в качестве ключей интервалы а не числа

только реализация окажется на порядок сложнее :-)
можно взять расширенное бинарное отсортированное дерево, в ноде будет два указателя и два поля с данными - начало и конец интервала
там будут ситуации, когда придется мержить две ноды в одну - что-то мне подсказывает, что в этом случае и гемора не оберешься, и накладные расходы будут ого-го
хотя все конечно зависит от структуры исходного массива

Т.е. время равно O(n)

0_0 ты хочешь сказать, что у тебя операции с хешем за O(1)? Ты получил решение в худшем случае за O(n^2*log(n)) (а то и за все O(n^3) при плохой реализации хеша) и это без учёта слияния диапазонов.

1 3 7 5 2 6 4

можно взять расширенное бинарное отсортированное дерево, в ноде будет два указателя и два поля с данными - начало и конец интервала там будут ситуации, когда придется мержить две ноды в одну - что-то мне подсказывает, что в этом случае и гемора не оберешься, и накладные расходы будут ого-го хотя все конечно зависит от структуры исходного массива.

Ну так ещё и дерево надо сбалансированное.

Найти самую длинную непрерывную последовательность

Ненужно.© Гугли монотонную посследовательность. Пример (внизу).

чтобы не быть голословным насчет времени поиска с хешем, привожу конкретный пример
я начал с 1 миллиона - время поиска составляет 1 секунду
затем увеличиваем генерируемый диапазон до 2 лимонов - и получаем 2 секунды
для 10 миллионов получаем даже меньше 10 секунд - т.е. время как-бы является линейной функцией , или я не прав ?

num =  []
print 'start generate ...'
for i in range(1,1000000):
  num.append(random.randint(1, 1000000)) 
print 'end generate ...'

def find2(arr):
    table = {}
    first = 0
    last = 0
    for i in arr:
        beg = end = i
        if i in table:
            continue
        table[i] = 'X'
        if i - 1 in table:
            beg = table[i-1]
        if i + 1 in table:
            end = table[i+1]
        table[beg] = end
        table[end] = beg
        if end - beg > last - first:
            first = beg
            last = end
    return list(range(first, last + 1))

print 'start search ...'
a = datetime.datetime.now()
rr = find2(num)
print 'end search ...'
print len(rr)
b = datetime.datetime.now()
c = b - a
print c

O(NlogN) + память под set. Всякие corner-case не рассматривал.

#include <iostream>
#include <set>
#include <iterator>
#include <algorithm>

using namespace std;

typedef pair<int,int> Coord;

struct Cmp { bool operator ()( const Coord &a, const Coord &b ) const { return a.first < b.first; } };

int main()
{
    int src[] = {1, 6, 10, 4, 7, 8, 3};
    typedef pair<int,int> Coord;
    set< Coord, Cmp > s;

    const size_t N = sizeof( src ) / sizeof( src[0] );
    for( int i=0; i<N; ++i )
    {
        s.insert( make_pair<int,int>( src[i], i ) );
    }

    int mono[N];
    int prev;

    set< Coord, Cmp >::const_iterator it = s.begin();
    for( int i = 0; it != s.end(); ++it, ++i )
    {
        if ( i != 0 )
        {
            mono[i] = ( it->second >= prev ) ? 1 : 0;
            prev = it->second;
        }
        else
        {
            prev = it->second;
        }
    }

    int start = 0;
    int maxCnt = 0;
    int cnt = 0;

    for( int i = 1; i < N; ++i )
    {
        cnt = ( mono[i] > 0 ) ? cnt + 1 : 0;

        if ( cnt > maxCnt )
        {
            start = i - cnt;
            maxCnt = cnt;
        }
    }

    //cout << start << ' ' << maxCnt << endl;

    // write output
    set< Coord, Cmp >::iterator it_b = s.begin();
    advance( it_b, start );

    for( int i = 0; i < maxCnt + 1; ++i )
    {
        cout << it_b->first << ' ';
        ++it_b;
    }
    cout << endl;

    return 0;
}

1. У тебя есть цикл от 1 до n, он даст нам множитель n. Внутри цикла есть операции вставки в хеш-таблицу и поиска в ней, это даст множитель от log(n) до n, в зависимости от реализации/ситуации. Итого O(n*log(n)) - O(n*n), в зависимости от реализации/ситуации.

2. Используй time.clock() для замера времени работы программы

3. Тебя не смутили секунды работы на миллионах чисел? Ты получил регресс => твоё псевдолинейное время работы программы

разьясни за счёт атомарности каких операций у тебя O(n) а не O(nlogn) ?

Сканирующий алгоритм
/thread

чтение доступ в ассоциативный массив отнюдь не О(1) а скорее логарифмический, уж про запись я вааще молчу;-)

Щито?

это даст множитель от log(n) до n,

Нет не даст. Единственное если рандом одно и тоже число будет выдавать.