如何獲得數組中的ascender元素？

Question

考慮一個由N個整數組成的零索引數組A.這個數組的索引是從0到N-1的整數。取一個指數K. 如果A [J]> A [K]，則指數J被稱爲K的上升。請注意，如果A [K]是數組A中的最大值，那麼K沒有上升。 如果abs（K-J）是最小可能值（即，如果J和K之間的距離最小），則K的上部J被稱爲K的最接近上升。 中，k最多可以有兩個最近的上升件：一個小，一個比K.

Answer 1

 1. Sort the array (if not pre-sorted) 
     2. Subtract every element with its adjacent element and store result in another 
      array. 
      Example: 1 3 5 6 8 -----> (after subtraction) 2 2 1 2 
     3. Find the minimal element in the new array. 
     4. Device a logic which would relate the minimal element in the new array to the 
      two elements in the original one. 

Answer 2

public class Solution { 
    final static int MAX_INTEGER = 2147483647; 

    public static int maximal(int[] A) { 
     int max = A[0]; 
     int length = A.length; 
     for (int i = 1; i < length; i++) { 
      if (A[i] > max) { 
       max = A[i]; 
      } 
     } 
     return max; 
    } 

public static int ascender(int[] a,int length, int k) { 
    int smallest = MAX_INTEGER; 
    int index = 0; 

    if (k<0 || k>length-1) { 
     return -1; 
    } 
    for (int i = 0; i < length; i++) { 
     // Index J is called an ascender of K if A[J] > A[K]. 
     if(a[i] > a[k]) { 
      int abs = Math.abs(i-k); 
      if (abs < smallest) { 

       smallest = abs; 

       index = i; 
      } 
     } 
    } 
    return index; 
} 


public static int[] array_closest_ascenders(int[] A) { 

    int length = A.length; 
    int[] R = new int[length]; 

    for (int K = 0; K < length; K++) { 

     // Note that if A[K] is a maximal value in the array A, 
        // then K has no ascenders. 
     // if K has no ascenders then R[K] = 0. 
     if (A[K] == maximal(A)) { 
      R[K] = 0; 
      break; 
     } 

     // 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 
     int J = ascender(A, A.length, K); 

     if (J != -1) { 

      R[K] = Math.abs(K - J); 
     } 

    } 
    return R; 
} 

public static void main(String[] args) { 
    int[] a = { 4, 3, 1, 4, -1, 2, 1, 5, 7 }; 
    /* int[] a = {-589630174, 806785750, -495838474, -648898313, 
      149290786, -798171892, 584782920, -288181260, -252589640, 
      133741336, -174886978, -897913872 }; */ 
    int[] R = array_closest_ascenders(a); 

    for (int element : R) { 
     System.out.print(element + " "); 
    } 
} 
} 

Answer 3

較大有關代碼的一些注意事項。我猜想break在array_closest_ascenders方法應該被替換爲continue，以便分析所有元素的上升。
當然，maximal(A)必須被移出循環;而是在進入循環之前將最大值分配給某個變量並在循環內使用，從而避免冗餘計算最大值。

Answer 4

// 
// C++ using multimap. -- INCOMPLETE 
// The multimap MM is effectively the "inverse" of the input array AA 
// since it is ordered by pair(value, index), where index refers to the index in 
// input array AA, and value is the value in AA at that index. 
// Input AA is of course ordered as (index, value). 
// So when we read out of MM in value order, (a sorted set of values), each value 
// is mapped to the index in the original array AA. 
// 
int ascender(int AA[], int N, int RR[]) { 

    multimap<int, int> MM; 

// simply place the AA array into the multimap 
    int i; 
    for (i = 0; i < N; i++) { 
     int value = AA[i]; 
     int index = i; 
     MM.insert(make_pair(value, index)); 
    } 

// simply read the multimap in order, 
// and set output RR as the distance from one value's 
// original index to the next value's original index. 
// 
// THIS code is incomplete, since it is wrong for duplicate values. 
// 
    multimap<int, int>::iterator pos; 
    for (pos = MM.begin(); pos != MM.end(); ++pos) { 
     int value = pos->first; 
     int index = pos->second; 
     ++pos;//temporarily move ahead to next item 
// NEED to FURTHER CONSIDER repeat values in setting RR 
     RR[index] = (pos)->second - index; 
     --pos; 
    } 


    return 1; 
} 

Answer 5

這裏是一個複雜度爲O（n）的C++解決方案。 請注意，有兩個循環，但每次迭代中元素的數量都是1/2的因子，或者搜索範圍上升了x2倍。例如，第一次迭代需要N次，但第二次迭代已經是N/2次。

vector<long> ascender(vector <long> A) 
{ 
    long N = A.size(); 
    vector<long> R(N,0); 
    vector<long> IndexVector(N,0); //This vector contains the index of elements with R=0 
    vector<long> RangeVector(N,0); //This vector define the loop range for each element 
    IndexVector[N-1]=N-1; 
    unsigned long CompxTest = 0; 


    for (long counter=0;counter<N;counter++) 
    { 
     IndexVector[counter] = counter; // we start that all elements needs to be consider 
     RangeVector[counter] = 1; // we start by looking only and neighbors 
    } 

    long Length = N; 
    long range; 

    while (Length>1) 
    { 
     long index = 0; 
     cout<<endl<<Length; 
     long J; 

     for (long counter=0;counter<Length;counter++) 
     { 

      CompxTest++; // Just to test complexity 

      J = IndexVector[counter]; // Get the index that need to be consider 
      range = RangeVector[J]; 

      //cout<<" ("<<A[J]<<","<<J<<")"; 

      if (range > N) 
      { 
       cout<<endl<<"Mini assert "<<range<<" N "<<N; 
       break; 
      } 

      if (J<(N-range) && A[J+range] > A[J]) 
      { 
       R[J] = range; 
      } 

      if (J<(N-range) && A[J+range] < A[J] && R[J+range]==0) 
      { 
       R[J+range] = range; 
      } 



      if (J<(N-range) && A[J] == A[J+range] && R[J+range]==0) 
      { 
       R[J+range] = - range; 

      } 

      if (R[J]==0) // Didn't find ascender for this element - need to consider in next iteration 
      { 
       if (R[J+range]>2) //We can increase the range because the current element is smaller 
        RangeVector[J] += R[J+range]-2; 
       if (R[J+range]<-2) 
        RangeVector[J] += -R[J+range]-2; 
       RangeVector[J]++; 

       IndexVector[index] = J; 
       index++; 
      } 
     } 


     Length = index; 

    } 

    for (long counter=0;counter<N;counter++) 
    { 
     if (R[counter] < 0) 
     { 
      unsigned Value = abs(R[counter]); 
      if (counter+Value<N && A[counter]<A[counter+Value]) 
       R[counter] = Value; 

      if (counter > Value && R[counter-Value]==0) 
       R[counter] = 0; 

      R[counter] = Value + R[counter-Value]; 

      if (counter > Value && Value < R[counter - Value]) 
      { 
       long PossibleSolution = R[counter - Value] + Value; 
       if (PossibleSolution <N && A[PossibleSolution]>A[counter]) 
        R[counter] = abs(counter - PossibleSolution); 

      } 


     } 
    } 

    cout<<endl<<"Complex "<<CompxTest; 

    return R; 

} 

Answer 6

這裏是C＃解決方案

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 7

基本上在搜索功能我比較數組的第一個元素與一個立即的權利，如果它是更大的，這意味着它是第一個最接近方興未艾。對於其他元素，我立即在左邊和右邊的元素之間進行比較。第一個是大是最接近方興未艾，我不斷重複這樣直到我沒有找到一個比一個大的元素我正在考慮要不我返回0

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; 
} 
}