排列順序/序列分析

Question

給出S個n個整數S = s1，s2，...，sn的序列。請計算如果 有可能將S分成兩部分：s1，s2，...，si和si + 1，si + 2，...，sn （n = i < n）第一部分嚴格減少，而第二部分嚴格增加一部分。首先以n爲輸入，然後再輸入n個整數，輸出是或否。

這就是我想

import java.util.Scanner; 

public class Sequence { 
    public static int c; 
    public static void main(String[] args) { 
     int n; 
     int count = 0; 
     Scanner s = new Scanner(System.in); 
     n = s.nextInt(); 
     int a[] = new int [n]; 
     for(int i = 0; i<n; i++)   // loop for taking input 
     { 
      a[i] = s.nextInt(); 
     } 
     for(int i = 0; i<n-2; i++)   // loop for finding the minimum point 
     { 
      if(a[i]<a[i+2]) 
      { c = i;      // associated minimum valued index to c 
       for(; i<n-2; i++)   /* loop for checking whether after that the array 
       {       is decreasing or not*/ 
        if(a[i+1]<a[i+2])   
        { 
         count = count+1; 
        } 
        else 
        { 

        } 
       } 

      } 
     if(count == n-2-c) 
     { 
      System.out.println("YES"); 
     } 
     else 
     { 
      System.out.println("NO"); 
     } 
     } 

    } 

這個代碼不經過1測試用例上Hackerrank.com請提出了一些解決方案。

Answer 1

做到這一點的一個好方法是通過二進制搜索：

您將有三個變量：lowbound，中，上界和 你從你的陣列和lowbounf = 0，上界= N-1的中間開始。

接下來，您將檢查數組的線性傳遞，如果s1，s2，... smiddle嚴格遞減並且smiddle，....，sn嚴格增加。如果是，那麼middle是您的解決方案。

如果s1，s2，... smiddle不是嚴格刪除和smiddle，.... sn，並不嚴格增加你沒有解決方案。如果s1，s2，... smiddle不是嚴格刪除和smiddle，....，sn嚴格增加，那麼uperbound = middle，middle =（upperbound + lowbound）/ 2，然後再試一次。如果s1，s2，... smiddle嚴格刪除並且smiddle，....，sn不是嚴格增加，那麼lowbound = middle，middle =（upperbound + lowbound）/ 2，然後再試一次。

直到您找到解決方案，或者發現沒有解決方案或直到lowbound = upperbound。

實施例：

序列：7 8 5 1 2 3 4 5 6 7 8 中間= 5（元件3），lowbound = 0，上界= 10，7,8,5,4,1 2,3不嚴格下降，而4,5,6,7,8嚴格遞增。

因此：上限= 5，中間= 2（元素數組[中間] = 2），7,8,5嚴格遞減，1,2,3,4,5,6,7,8嚴格（注意middle = 2意味着是數組的第三個元素，第一個是數組[0]，第二個是數組[1]，第三個是數組[2] = array [middle] = 5）。

上面的解決方案嘗試log n次（由於二分查找）線性檢查數組（每個線性檢查是O（n））。因此，此解決方案是O（n log n）。