Нахождение смежных диапазонов в массивах

Question

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

{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15}

Здесь мы находим два (нетривиальных) диапазона, для которых в массиве присутствуют все целые числа из этих диапазонов, а именно [2,8] и [10,12].Из них [2,8] более длинный.Поэтому нам нужно вывести это.

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

Вот моя попытка решения:

void printRange(int arr[])
{
    int n=sizeof(arr)/sizeof(int);
    int size=2;
    int tempans[2]; 

    int answer[2];// the range is stored in another array
    for(int i =0;i<n;i++)
    {
        if(arr[0]<arr[1])
        {
             answer[0]=arr[0];
             answer[1]=arr[1];
        }
        if(arr[1]<arr[0])
        {
            answer[0]=arr[1];
            answer[1]=arr[0];
        }

        if(arr[i] < answer[1])
            size += 1;
        else if(arr[i]>answer[1]) {
            initialize tempans to new range;
             size2=2;
        }
        else { 
            initialize tempans  to new range
        }
}

//I have to check when the count becomes equal to the diff of the range

Я застрял в этой части... Я не могу понять, сколько массивов tempanswer [] следует использовать.

Answer 1

Я думаю, что следующее решение будет работать за время O (n) с использованием пространства O (n).

Начните с помещения всех записей в массиве в хеш-таблицу.Затем создайте вторую хеш-таблицу, в которой хранятся элементы, которые мы «посетили» и которые изначально были пустыми.

Теперь итерируйте по массиву элементов по одному за раз.Для каждого элемента проверьте, находится ли элемент в посещаемом наборе.Если так, пропустите это.В противном случае, посчитайте от этого элемента вверх.На каждом шаге проверяйте, находится ли текущий номер в основной хеш-таблице.Если это так, продолжайте и отметьте текущее значение как часть посещенного набора.Если нет, остановись.Далее повторите эту процедуру, кроме как считать вниз.Это говорит нам о количестве смежных элементов в диапазоне, содержащем это конкретное значение массива.Если мы будем отслеживать самый большой диапазон, найденный таким образом, у нас будет решение нашей проблемы.

Сложность этого алгоритма во время выполнения - O (n).Чтобы увидеть это, обратите внимание, что мы можем построить хеш-таблицу на первом шаге за O (n) времени.Затем, когда мы начинаем сканирование в массив, чтобы найти самый большой диапазон, каждый сканированный диапазон занимает время, пропорциональное длине этого диапазона.Поскольку общая сумма длин диапазонов - это количество элементов в исходном массиве, и поскольку мы никогда не сканируем один и тот же диапазон дважды (потому что мы помечаем каждое посещаемое число), этот второй шаг занимает время O (n) какну, для чистого времени выполнения O (n).

РЕДАКТИРОВАТЬ: Если вам интересно, у меня есть реализация Java изэтот алгоритм вместе с гораздо более подробным анализом того, почему он работает и почему он имеет правильное время выполнения.Также рассматриваются некоторые крайние случаи, которые не очевидны в начальном описании алгоритма (например, как обрабатывать целочисленное переполнение).

Надеюсь, это поможет!

Answer 2

Решение может использовать BitSet:

public static void detect(int []ns) {
    BitSet bs = new BitSet();
    for (int i = 0; i < ns.length; i++) {
        bs.set(ns[i]);
    }
    int begin = 0;
    int setpos = -1;
    while((setpos = bs.nextSetBit(begin)) >= 0) {
        begin = bs.nextClearBit(setpos);
        System.out.print("[" + setpos + " , " + (begin - 1) + "]");
    }
}

Пример ввода / вывода:

detect(new int[] {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15} );

[2,8] [10,12] [15,15]

Answer 3

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

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

def longestConsecutive(self, nums):
    nums = set(nums)                    # Create Hash O(1)   
    best = 0
    for x in nums:                   
        if x - 1 not in nums:           # Optimization
            y = x + 1                   # Get possible next number
            while y in nums:            # If the next number is in set/hash
                y += 1                  # keep counting
            best = max(best, y - x)     # counting done, update best
    return best

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

Все кредиты Стефану Похманну.

Answer 4

Быстрый способ сделать это (PHP):

$tab = array(14,12,1,5,7,3,4,10,11,8);
asort($tab);
$tab = array_values($tab);
$tab_contiguous = array();
$i=0;
foreach ($tab as $key => $val) {
    $tab_contiguous[$i][] = $tab[$key];
    if (isset($tab[$key+1])) {
        if($tab[$key] + 1 != $tab[$key+1])
            $i++;
    }
}
echo(json_encode($tab_contiguous));

Answer 5

Вот решение на Java:

public class Solution {  
    public int longestConsecutive(int[] num) {  
        int longest = 0;  
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
        for(int i = 0; i< num.length; i++){  
            map.put(num[i], false);  
        }  

        int l, k;  
        for(int i = 0;i < num.length;i++){  

            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;  
            map.put(num[i], true);  
            l = 0; k = num[i];  
            while (map.containsKey(k)){  
                l++;  
                k++;  
            }  
            if(longest < l) longest = l;  

        }  
        return longest;  
    }  
}  

Другие подходы здесь .

Answer 6

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

import qualified Data.HashTable.IO as H
import Control.Monad.Random

f list = do 
  h <- H.new :: IO (H.BasicHashTable Int Int)
  g list (0,[]) h where
    g []     best h = return best
    g (x:xs) best h = do 
      m <- H.lookup h x
      case m of
        Just _     -> g xs best h
        otherwise  -> do 
          (xValue,newRange) <- test
          H.insert h x xValue
          g xs (maximum [best,newRange]) h
       where 
         test = do
           m1 <- H.lookup h (x-1)
           m2 <- H.lookup h (x+1)
           case m1 of
             Just x1 -> case m2 of
                          Just x2 -> do H.insert h (x-1) x2
                                        H.insert h (x+1) x1
                                        return (x,(x2 - x1 + 1,[x1,x2]))
                          Nothing -> do H.insert h (x-1) x
                                        return (x1,(x - x1 + 1,[x,x1]))
             Nothing -> case m2 of
                          Just x2 -> do H.insert h (x+1) x
                                        return (x2,(x2 - x + 1,[x,x2]))
                          Nothing -> do return (x,(1,[x]))

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100,100)

main = do
  values <- evalRandIO (sequence (replicate (1000000) rnd))
  f values >>= print

Выход:

*Main> main
(10,[40,49])
(5.30 secs, 1132898932 bytes)

Answer 7

На самом деле, учитывая, что мы сортируем только целые числа и, следовательно, сортировка сравнения НЕ обязательна, вы можете просто отсортировать массив с помощью Radix- или BucketSort, а затем выполнить итерацию по нему.

Просто и, конечно, не то, чтоинтервьюируемый хотел услышать, но, тем не менее, исправить;)

Answer 8

Приведенный выше ответ по шаблону будет работать, но вам не нужна хеш-таблица. Хэширование может занять много времени в зависимости от того, какой алгоритм вы используете. Вы можете спросить интервьюера, есть ли максимальное число, которым может быть целое число, а затем создать массив такого размера. Назовите его как существующее [] Затем просмотрите arr и отметьте существующее [i] = 1; Затем выполните итерацию по существующему [], отслеживая 4 переменные, размер текущего наибольшего диапазона и начало текущего наибольшего диапазона, размер текущего диапазона и начало текущего диапазона. Когда вы увидите, что существует [i] = 0, сравните текущие значения диапазона с самыми большими значениями диапазона и при необходимости обновите самые большие значения диапазона.

Если нет максимального значения, возможно, вам придется использовать метод хеширования.