Как сделать время выполнения O (N) от O (N^2)

Question

Я попытался решить одну проблему программирования (ни моя домашняя работа, ни мое интервью/тест, но может быть хорошим кандидатом) в Интернете. Проблема приведена ниже. Мой код ниже функционально корректен, но он имеет сложность времени выполнения O (N), где в качестве ожидаемого решения должно быть значение O (N).

Я попробовал пару других подходов, чтобы оптимизировать его - 1) Сортировал массив, а затем попытался, если бы я мог заставить это работать, но поскольку сортировка приводит к потере индексов исходных чисел, я даже сохранил их в отдельном массив, и сделал это, но даже это закончилось тем, что O (N). Я уверен, что сортировка массива поможет здесь добраться до O (N), но просто не сможет прибить его.

Любая помощь в решении этой проблемы в O (N) с использованием любого подхода была бы полезна.

(Извиняюсь за длинный пост)

Рассмотрим нулевой индексированный массив из N целых чисел. Индексами этого массива являются целые числа от 0 до N-1. Возьмем индекс K. Индекс J называется возведением А, если A [J]> A [K]. Заметим, что если A [K] является максимальным значением в массиве A, то K не имеет восходящих линий.

Ascender J of K называется ближайшим выступающим элементом K, если abs (K-J) является наименьшим возможным значением (т. Е. Если расстояние между J и K минимально). Обратите внимание, что К может иметь не более двух ближайших восходящих: один меньше и больше, чем один К.

Например, рассмотрим следующий массив:

А [0] = 4 А [1] = 3 A [2] = 1 A [3] = 4 A [4] = -1 A [5] = 2 A [6] = 1 A [7] = 5 A [8] = 7

Если K = 3, то к имеет два восходящие: 7 и 8. Его ближайшие восходящий 7 расстояние между K и 7 равна абсом (к-7) = 4.

Написать функцию:

struct Results { 
    int * R; 
    int N; 
}; 

struct Results array_closest_ascenders(int A[], int N); 

, что при нулевой индексированный массив А целых чисел N, возвращает нулевой индексированный массив R из N целых чисел, таких, что (при К = 0, ..., N-1):

if K has the closest ascender J, then R[K] = abs(K−J); that is, R[K] is equal to the distance between J and K, 
    if K has no ascenders then R[K] = 0. 

Например, для следующей матрицы A:

A [0] = 4 A [1] = 3 A [2] = 1 A [3] = 4 A [4] = -1 A [5] = 2 А [6] = 1 А [7] = 5 А [8] = 7

функция должна возвращать следующий массив R:

R [0] = 7 R [1] = 1 R [ 2] = 1 R [3] = 4 R [4] = 1 R [5] = 2 R [6] = 1 R [7] = 1 R [8] = 0

Массив R должен быть возвращен как:

a structure Results (in C), or 
    a vector of integers (in C++), or 
    a record Results (in Pascal), or 
    an array of integers (in any other programming language). 

Предположим, что:

N is an integer within the range [0..50,000]; 
    each element of array A is an integer within the range [−1,000,000,000..1,000,000,000]. 

Сложность:

expected worst-case time complexity is O(N); 
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). 

Элементы входных массивов могут быть изменены.

Мое решение (O (N 2 )):

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

struct Results 
{ 
    int *R; 
    int N; 
}; 

struct Results array_closest_ascenders (int A[], int N) 
{ 
    struct Results result; 


    int i,j,asc_found=0; 

    result.R = (int*)malloc(sizeof(int)*N); 

    for(i=0;i<N;i++) 
     result.R[i] = N; 

    result.N = N; 

    for(i=0;i<N;i++) 
    { 
     asc_found = 0; 
     for(j=0;j<N;j++) 
     { 
     if(A[i] < A[j]) 
     { 
      //if(result.R[i] == 0) 
      { 
       if(result.R[i] > abs(i-j)) 
       { 
        result.R[i] = abs(i-j); 
        asc_found = 1; 
       } 
      } 
     } 
     } 
     if(asc_found == 0) 
      result.R[i] = 0; 
    } 


    return result; 
} 

void main() 
{ 

    //int A[] = {4, 3, 1, 4, -1, 2, 1, 5, 7}; 
    int A[] = {691446939, -241956306, 485954938, 604054438, 383714185, -656099986, -357341170, -255988102, -139683363, -463281394, -382925609, 712727854}; 
    struct Results tmp; 

    tmp = array_closest_ascenders(A,sizeof(A)/sizeof(A[0])); 

} 

Answer 1

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

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

for i in 0 .. N 
    while (!stack.empty) && (A[stack.top] <= A[i]) 
    stack.pop 
    if stack.empty 
    then R[i] = 0 
    else R[i] = i - stack.top 
    stack.push(i) 

Answer 2

Я имею в виду, чтобы добавить это в качестве комментария, но никаких комментариев ссылка не показывает. Не следует ли R [] следовать?

R[0]=abs(0-7)=7; 
R[1]=abs(1-0)=1; 
R[2]=abs(2-5)=3; 
R[3]=abs(3-7)=4; 
R[4]=abs(4-2)=2;/or 4-6 
R[5]=abs(5-1)=4; 
R[6]=abs(6-5)=1; 
R[7]=abs(7-8)=1; 
R[8]=abs(8-8)=0; 

Основываясь на вашем комментарии ниже, вот программа, которая работает. Алгоритм основан на подсчете сортировки (как представлено на http://geekviewpoint.com/Sort_Algorithms_in_java/). «Смещение» должно допускать отрицательные значения, такие как «-1»

ПРИМЕЧАНИЕ. Несмотря на наличие вложенного цикла для заполнения R [], алгоритм не является N^2, потому что второй цикл итерирует по числу ведер.

ОТВЕТ: [7, 1, 1, 4, 1, 2, 1, 1, 0]

import java.util.ArrayList; 
import java.util.Arrays; 

public class Ascender { 
public static int[] ascenderArray(int[] A) { 
    int max = A[0], min = A[0]; 
    for (int i : A) { 
     if (max < i) 
      max = i; 
     if (min > i) 
      min = i; 
    } 
    int offset = min < 0 ? -min : 0; 
    ArrayList<Integer> buckets[] = new ArrayList[max + 1 + offset]; 
    for (int i = 0; i < buckets.length; i++) 
     buckets[i] = new ArrayList<Integer>(); 
    for (int i = 0; i < A.length; i++) 
     buckets[A[i] + offset].add(i); 

    int[] R = new int[A.length]; 
    for (int i = 0; i < R.length; i++) { 
     try { 
      min = A.length; 
      int x = A[i] + 1 + offset; 
      for (int n = x; n < buckets.length; n++) { 
       x=n; 
       while (buckets[x].isEmpty()) 
        x++; 
       n=x; 
       int tmp = Math.abs(i - buckets[n].get(0)); 
       if (min > tmp) 
        min = tmp; 
      } 
      R[i] = min==A.length?0:min; 
     } catch (Exception e) { 
      R[i] = 0; 
     } 
    } 
    return R; 
}// 

public static void main(String... args) { 
    int A[] = { 4, 3, 1, 4, -1, 2, 1, 5, 7 }; 
    int R[] = ascenderArray(A); 
    System.out.println(Arrays.toString(R)); 
} 
} 

Answer 3

Я не уверен, если есть Ο решения (N), но здесь есть О (N · журнала N) решения в JavaScript:

var A = [4,3,1,4,-1,2,1,5,7], 
    N = A.length; 

// build an array of index:value pairs and sort them in ascending order 
var sorted = []; 
for (var i=0; i<N; i++) { 
    sorted.push({index:i, value:A[i]}); 
} 
sorted.sort(function(a, b) { return a.value - b.value; }); 

// iterate the sorted array in descending order 
var ascenders = [], 
    closest,   // closest ascender 
    curr = sorted[N-1]; // initiate curr with largest item 
ascenders[N-1] = 0; 
for (var i=N-2; i>=0; i--) { 
    // compare curr from the previous iteration with the future 
    // curr of the current iteration 
    if (sorted[i].value !== curr.value) { 
     // update closest ascender if their values differ 
     closest = curr; 
    } 
    curr = sorted[i]; 
    ascenders[i] = Math.abs(curr.index-closest.index); 
} 

// rearrange ascenders in the original order 
var ret = []; 
for (var i=0; i<N; i++) { 
    ret[sorted[i].index] = ascenders[i]; 
} 

Здесь сортировка значений является наибольшим усилием Ο (N · log N).

Answer 4

import java.util.Arrays; 
import java.util.TreeMap; 

public class AsenderUtil { 

    public static int[] getClosestAsenderIndices(int[] arr, int indx) { 

     if (indx < 0 || arr.length <= indx) 
      throw new RuntimeException("wrong input"); 

     int baseVal = arr[indx]; 

     TreeMap<Integer,Integer> ts = new TreeMap<Integer,Integer>(); 

     for(int i=0;i<arr.length;i++){ 
      if(arr[i]>baseVal) { 
       ts.put(Math.abs(i-indx),i); 
      } 
     } 

     int[] toReturn = new int[2]; 
     toReturn[0] = ts.remove(ts.firstKey()); 
     toReturn[1] = ts.remove(ts.firstKey()); 

     return toReturn; 
    } 

    public static void main(String... args) { 
     int A[] = { 4, 3, 1, 4, -1, 2, 1, 5, 7 }; 
     int R[] = getClosestAsenderIndices(A,3); 
     System.out.println(Arrays.toString(R)); 
    } 
} 

Answer 5

class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] A = new int[] { 4, 3, 1, 4, -1, 2, 1, 5, 7 }; 
     int[] B = new int[A.Length]; 
     int[] R = new int[A.Length]; 
     Program obj = new Program(); 
     obj.ABC(A,B, R); 
    } 

    public void ABC(int[] A,int[]B, int[] R) 
    { 
     int i, j, m,k; 
     // int temp = 0; 
     int n = A.Length - 1; 
     for (i = 0; i < n; i++) 
     { 
      for (j = 0; j <= n; j++) 
      { 
       if (A[i] < A[j]) 
       { 
        m = Math.Abs(j - i); 
        R[i] = m; 
        break; 

       } 

      } 
      for (j = i-1; j > 0; j--) 
      { 
       if (A[i] < A[j]) 
       { 
        k = Math.Abs(j - i); 
        B[i] = k; 
        break; 

       } 

      } 

     } 
     for (i = 0; i < n; i++) 
     { 
      if (R[i] > B[i] && (B[i] == 0)) 
      { 

       R[i] = R[i]; 
       //Console.WriteLine(R[i]); 
       //Console.ReadLine(); 
      } 

      else { R[i] = B[i]; } 
     } 


    } 
} 

Answer 6

Мое решение O (N):

class ArrayClosestAscendent { 
public int[] solution(int[] A) { 
    int i; 
    int r[] = new int[A.length]; 
    for(i=0;i<A.length;i++){ 
     r[i] = search(A, i); 
    } 
    return r; 
} 

public int search(int[] A, int i) { 
    int j,k; 
    j=i+1; 
    k=i-1; 
    int result = 0; 
    if(j <= A.length-1 && (A[j]>A[i])) 
      return Math.abs(j-i); 
    j++; 
    while(k>=0 || j < A.length){ 
     if(k >= 0 && A[k] > A[i]){ 
      return Math.abs(i-k); 
     }else if(j < A.length && A[j] > A[i]){ 
      return Math.abs(i-j); 
     }else{ 
      j++; 
      k--; 
     } 
    } 
    return result; 
}  
} 

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