Массив с последовательными номерами - Алгоритм

Question

Я пытаюсь ответить на следующий вопрос: учитывая отсортированный массив с некоторыми упорядоченными числами и некоторыми непересекающимися числами, напишите алгоритм, который получает пару {start, end} для каждой группы последовательных номера. У последовательных номеров есть разница только 1.

До сих пор я могу думать только грубой силы метод:

public static void main(String[] args) { 
    int[] array = { 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27 }; 
    Map<Integer, Integer> list = new HashMap<Integer, Integer>(); 

    list = findIndex(array); 
} 

// Bruteforce 
private static Map<Integer, Integer> findIndex(int[] array) { 
    Map<Integer, Integer> list = new HashMap<Integer, Integer>(); 

    int x = -1, y = -1; 

    int end = array.length; 
    for (int i = 0; i < end; i++) { 
     x = i; 
     while (i < end - 1) { 

      if (array[i] + 1 == array[i + 1]) { 
       i++; 
       y = i; 
      } else { 
       if (x != y && x >= 0) { 
        list.put(x, y); 
        System.out.println("i = " + x + " to j = " + y); 
        i = i + 1; 
        break; 
       } 
      } 
     } 

    } 
    return list; 
} 

Выход:

i = 0 to j = 5 
i = 7 to j = 10 
i = 12 to j = 14 

Он отлично работает, но как я могу улучшить временную сложность?

Answer 1

Вам не нужно гнездо петли для этого:

int end = array.length; 
if (end > 0) { 
    int start = 0; 
    for (int i = 1; i < end; i++) { 
     if (array[i] != array[i - 1] + 1) { 
      if (i - start > 1) { 
       list.put(start, i - 1); 
       System.out.println("i = " + start + " to j = " + (i - 1)); 
      } 
      start = i; 
     } 
    } 
    if (end - start > 1) { 
     list.put(start, end - 1); 
     System.out.println("i = " + start + " to j = " + (end - 1)); 
    } 
} 

Answer 2

Как только отсортированный начальный массив, вы можете иметь O (N) реализацию этого алгоритма, как это:

private static Map<Integer, Integer> getConsecutive(final int[] array) { 
    final Map<Integer, Integer> list = new TreeMap<Integer, Integer>(); 
    int startIndex = 0; 
    int endIndex = 0; 
    for (int i = 1; i < array.length; i++) { 
     if (array[i - 1] + 1 == array[i]) 
      endIndex = i; 
     else { 
      if (endIndex > startIndex) 
       list.put(startIndex, endIndex); 
      startIndex = endIndex = i; 
     } 
    } 
    if (endIndex > startIndex) 
     list.put(startIndex, endIndex); 
    return list; 
}