Найти число в массиве

Ответ 1

Да, это может быть сделано в O(n) времени. Далее следуют несколько методов.

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

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

# Set current values.

highLeftVal = cell[0]
lowRightVal = cell[cell.lastIndex]

# For running right and left through array.

rightIdx = cell.lastIndex
for each leftIdx 1 thru cell.lastIndex inclusive:
    # Left index done by loop, right one manually.

    rightIdx = rightIdx - 1

    # Store current values and update.

    highLeft[leftIdx] = highLeftVal
    if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]

    lowRight[rightIdx] = lowRightVal
    if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]

Тогда просто проверить каждую ячейку (сначала первую и последнюю), чтобы убедиться, что значение больше, чем (этот ответ предполагает, согласно вашему вопросу, что "выше/ниже" является буквальным, а не "большим/меньше или равно" ) наивысший слева и меньше самого низкого справа:

for each idx 1 thru cell.lastIndex-1 inclusive:
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]
        print "Found value ", cell[idx], " at index ", idx

Ниже вы можете увидеть результаты начального прохода:

highLeft:   -  1  3  3  6  6  7  9  9 10 10
cells   :   1  3  2  6  5  7  9  8 10  8 11
lowRight:   2  2  5  5  7  8  8  8  8 11  -
                           ^

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

Теперь имейте в виду, что это относительно простое решение, которое может найти несколько элементов, удовлетворяющих ограничениям. Учитывая, что вам нужен только один элемент, можно получить лучшую производительность (хотя он все еще O (n)).

Основная идея состоит в том, чтобы пересечь массив слева направо, и для каждой ячейки вы проверяете, все ли слева, и все справа выше.

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

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

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

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

Этот поиск происходит из текущей точки, а не в начале, потому что:

• все после того, как текущий ответ до, но исключая эту (меньшую или равную) ячейку, больше, чем текущий ответ, иначе вы бы уже нашли меньшую или равную ячейку; и
• эта ячейка должна быть меньше или равна каждой ячейке в этом диапазоне, поскольку она меньше или равна текущему ответу; Поэтому
• никакая ячейка в этом диапазоне не действительна, все они больше или равны этому.

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

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

Следовательно, псевдокод для этого зверя выглядит примерно так:

# Store max on left and start with sentinel.

maxToLeft = cell[0]
answer = -1

for checking = 1 to cell.lastIndex-1 inclusive:
    switch on answer:
        # Save if currently sentinel and item valid.
        case -1:
            if cell[checking] > maxToLeft:
                answer = checking

        # Set back to sentinel if saved answer is now invalid.
        otherwise:
            if cell[answer] >= cell[checking]:
                answer = -1

    # Ensure we have updated max on left.

    if cell[checking] > maxToLeft:
        maxToLeft = cell[checking]

# Final check against last cell.

if answer != -1:
    if cell[cell.lastIndex] <= cell[answer]:
        answer = -1

Поскольку мой псевдокод (в значительной степени) основан на Python, довольно простой вопрос - предоставить более конкретный пример кода в действии. Во-первых, опция "найти любую возможность":

cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]

highLeft = [0] * len(cell)
lowRight = [0] * len(cell)

highLeftVal = cell[0]
lowRightVal = cell[len(cell)-1]

rightIdx = len(cell) - 1
for leftIdx in range(1, len(cell)):
    rightIdx = rightIdx - 1

    highLeft[leftIdx] = highLeftVal
    if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]

    lowRight[rightIdx] = lowRightVal
    if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]

print(highLeft)
print(cell)
print(lowRight)

for idx in range(1, len(cell) - 1):
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
        print("Found value", cell[idx], "at index", idx)

И второй, немного более эффективный вариант, но только способный найти одну возможность:

cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
maxToLeft = cell[0]
answer = -1
for checking in range(1, len(cell) - 1):
    if answer == -1:
        if cell[checking] > maxToLeft:
            answer = checking
    else:
        if cell[answer] >=cell[checking]:
            answer = -1
    if cell[checking] > maxToLeft:
        maxToLeft = cell[checking]

if answer != -1:
    if cell[len(cell] - 1] <= cell[answer]:
        answer = -1

if answer == -1:
    print ("Not found")
else:
    print("Found value", cell[answer], "at index", answer);


print(highLeft)
print(cell)
print(lowRight)

for idx in range(1, len(cell) - 1):
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
        print("Found value", cell[idx], "at index", idx)

Вывод обоих из них (хотя последний пример показывает только конечную строку) показывает в основном то, что означал псевдокод:

[0, 1, 3, 3, 6, 6, 7, 9, 9, 10, 10]
[1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
[2, 2, 5, 5, 7, 8, 8, 8, 8, 11, 0]
Found value 7 at index 5

Ответ 2

Вот O (n), однопроходное решение в Python. Порт на Java тривиален:

import random
A = [random.randint(1, 10) for i in range(0, 5)] # Generate list of size 5.
max_seen = A[0]
candidate = None
for i in range(1,len(A)):
  if candidate is None:
    if A[i] > max_seen:
      candidate = i
  else:
    if A[i] <= A[candidate]:
      candidate = None
  max_seen = max(max_seen, A[i])

print("Given %s " % (A,))
if candidate is not None and candidate != len(A)-1: # Ignore the last element as per spec.
  print("found: value=%d; index=%d\n" % (A[candidate], candidate))
else:
  print("not found")

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

Описание

Задача восстановления: найти индекс я элемента в массиве A, так что все A [j], j < я = > A [j] A [i] и все A [k], k > я = > A [k] > A [i]. Первый такой элемент - один из таких элементов, поэтому мы просто находим первый.

Учитывая индекс x, если x удовлетворяет указанному выше условию, тогда A [x] > A [0..x-1] и A [x] А [х + 1..A.length]. Достаточно проверить обе эти ограничения для данного х. Примечание A [x] > A [0..x-1] <= > A [x] > max (A [0..x-1]). Таким образом, мы сохраняем максимальное значение, увиденное до сих пор, находим первое x, удовлетворяющее условию 1, и выполняем итерацию по проверке состояния 2. Если условие 2 никогда не проверяется, мы знаем, что следующий возможный кандидат находится за пределами текущего индекса, y, потому что A [x..y-1] > A [x] = > A [y] A [x..y-1], и больше, чем максимальное значение, наблюдаемое до сих пор.

Ответ 3

Создайте один дополнительный массив, который вычисляется путем перемещения слева направо в исходном массиве. Для любого индекса N в этом массиве значение является наивысшим значением, наблюдаемым между 0: N-1 в первом массиве.

int arr1 = new int[source.length];
int highest = MIN_INT;
for (int i = 0; i < source.length; i++) {
    arr1[i] = highest;
    if (source[i] > highest) {
        highest = source[i];
    }
}

Теперь создайте второй массив, который формируется путем сканирования справа налево, где любое значение в индексе N представляет наименьшее значение, наблюдаемое между N + 1: end

arr2 = new int[source.length];
int lowest = MAX_INT;
for (int i = (source.length-1); i <= 0; i--) {
    arr2[i] = lowest;
    if (source[i] < lowest) {
        lowest = source[i];
    }
}

Теперь у вас в основном есть три массива:

source: 1   3   2   6   5  7   9   8   10   8   11
arr1:   MIN 1   3   3   6  6   7   9    9  10   10
arr2:   2   2   5   5   7  8   8   8    8  11   MAX

Теперь вы просто хотите сканировать все три массива вместе, пока не найдете индекс, где это условие выполняется:

arr1[i] < source[i] < arr2[i] 

where:
     0 < i < (source.length-1)

код:

for (int i = 1; i < (source.length-1); i++) {
    if ((arr1[i] < source[i]) && (source[i] < arr2[i])) {
        return i; // or return source[i]
    }
}

Это время O (N).

Ответ 4

Я написал реализацию в c, используя алгоритм из S.Pinkus answer, с информацией отладки.

код

find_mid_num.c:

/**
 * Problem:
 *  there is an array of number, find an element which is larer than elements before it, and smaller than elements after it,
 *  refer:  http://stackoverflow.com/questions/41293848
 * 
 * Solution:
 *  loop through array, remember max value of previous loopped elements, compare it to next element, to check whether the first condition is met,
 *  when found an element met the first condition, then loop elements after it to see whether second condition is met,
 *  if found, then that it; if not found, say at position 'y' the condition is broken, then the next candidate must be after y, thus resume the loop from element after y,
 *  until found one or end of array,
 * 
 * @author Eric Wang
 * @date 2016-12-23 17:08
 */
#include <stdio.h>

// find first matched number, return its index on found, or -1 if not found,
extern int findFirstMidNum(int *arr, int len);

int findFirstMidNum(int *arr, int len) {
    int i=0, j;
    int max=arr[0];

    while(i < len) {
        printf("\n");
        if(arr[i] <= max) {
            printf("give up [%d]-th element {%d}, 1st condition not met\n", i, arr[i]);
            i++;
            continue;
        }
        max = arr[i]; // update max,

        printf("checking [%d]-th element {%d}, for 2nd condition\n", i, arr[i]);
        j = i+1;
        while(j < len) {
            if(arr[j] <= max) {
                printf("give up [%d]-th element {%d}, 2nd condition not met\n", i, arr[i]);
                break;
            }
            j++;
        }
        printf("position after 2nd check:\ti = %d, j = %d\n", i, j);

        if(j==len && j>i+1) {
            return i;
        } else {
            max = arr[j-1]; // adjust max before jump,
            i = j+1; // jump
            printf("position adjust to [%d], max adjust to value {%d}, after 2nd check\n", i, arr[j-1]);
        }
    }

    return -1;
}

int main() {
    int arr[] = {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
    int len = sizeof(arr)/sizeof(arr[0]);
    printf("\n============ Input array ============\n");
    printf("size:\t%d\n", len);
    printf("elements:\t{");

    int i;
    for(i=0; i<len; i++) {
        printf("%d, ", arr[i]);
    }
    printf("}\n\n");

    printf("\n============ Running info ============\n");
    int pos = findFirstMidNum(arr, len);

    printf("\n============ Final result============\n");
    if (pos < 0) {
        printf("Element not found.\n");
    } else {
        printf("Element found at:\n\t position [%d], with value: {%d}\n", pos, arr[pos]);
    }
    printf("\n");

    return 0;
}

Compile:

gcc -Wall find_mid_num.c

Execute:

./a.out

Результат выполнения:

============ Input array ============
size:   11
elements:   {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11, }


============ Running info ============

give up [0]-th element {1}, 1st condition not met

checking [1]-th element {3}, for 2nd condition
give up [1]-th element {3}, 2nd condition not met
position after 2nd check:   i = 1, j = 2
position adjust to [3], max adjust to value {3}, after 2nd check

checking [3]-th element {6}, for 2nd condition
give up [3]-th element {6}, 2nd condition not met
position after 2nd check:   i = 3, j = 4
position adjust to [5], max adjust to value {6}, after 2nd check

checking [5]-th element {7}, for 2nd condition
position after 2nd check:   i = 5, j = 11

============ Final result============
Element found at:
     position [5], with value: {7}

TODO - Дальнейшие улучшения:

• Проверить граничные элементы.
• Предоставьте функцию сорта, чтобы найти все такие элементы, а не только первый.

Ответ 5

Это имеет значение O (n) как для сложности времени и пространства, так и для одного массива Pass.

Логика:

• Найти первое максимальное и общее максимальное число, найденное до сих пор, продолжать перемещение массива до тех пор, пока вы не найдете значение, меньшее, чем first_max.
• Если вы это сделали, оставите first_max и все элементы до этого, так как все эти элементы были больше, чем мой текущий элемент.
  
• Теперь выберите first_max так, чтобы следующее значение было больше, чем total_max, который мы все находили.

Код:

// int[] arr = { 10, 11, 1, 2, 12, 13, 14};
int[] arr = {  1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
Integer firstMax = null;
Integer overallMax = null;

for (int i = 1; i < arr.length - 1; i++) {
    int currentElement = arr[i];
    if (firstMax == null) {
        if (overallMax == null) {
            firstMax = currentElement;
        } else if (overallMax != null && currentElement > overallMax) {
            firstMax = currentElement;
        }
    }
    if (overallMax == null || currentElement > overallMax) {
        overallMax = currentElement;
    }
    if (firstMax != null && currentElement < firstMax) {
        // We found a smaller element, so all max found so far is useless. Start fresh.
        firstMax = null;
    }
}

System.out.println(firstMax);

PS: Из моего анализа я считаю, что этого должно быть достаточно и работать во всех случаях. Не уверен, что пропущен какой-либо случай.