Подтвердить что ты не робот

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

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

{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 [] должно использоваться.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

Ответ 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]

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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)

Ответ 6

Вот решение в 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;  
    }  
}

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

Ответ 7

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

Основой этого метода является создание set/hash, который принимает O (n) время, и отсюда каждый доступ к set/hash будет O (1). Поскольку O-Notation опускает постоянные члены, этот алгоритм все еще можно описать как 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 последовательности.

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

Ответ 8

Быстрый способ сделать это (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));