排列顺序/顺序分析

Question

给你一个 n 个整数序列 S = s1, s2, ..., sn。请计算如果可以将 S 分成两部分：s1, s2, ..., si 和 si+1, si+2, ...., sn (1 <= 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");
        }
        }

    }

此代码未通过 Hackerrank.com 上的 1 个测试用例，请提出一些解决方案。

Answer 1

一个好的方法是二分查找：

您将拥有三个变量：低限、中限、上限和你从数组的中间开始，lowbounf=0,upperbound =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 middle=5(元素3),lowbound=0,upperbound=10,7,8,5,4,1,2,3不严格递减,4,5,6,7,8严格递增.

so:upperbound=5,middle=2(元素数组[middle]=2),7,8,5是严格递减的,1,2,3,4,5,6,7,8是严格增加，所以解决方案是 middle = 2 。（注意 middle=2 意味着它是数组的第三个元素，第一个是 array[0]，第二个是 array[1]，第三个是 array[2]=array[middle] =5 ).

上面的解决方案是尝试 log n 次（由于二进制搜索）来线性检查数组（每次线性检查都是 O(n)）。所以这个解决方案是 O(n log n)。

Answer 2

import java.util.*;
public class Main {

    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int f=0;
      int arr[]=new int[n];
        for(int i=0;i<n;i++)
        {
          arr[i]=sc.nextInt();
        }
      int i=0;
      for(i=0;i<n-1;i++)
      {
        if(arr[i]<arr[i+1])
        {
           break;
        }

      }
      for(int j=i+1;j<n-1;j++)
       if(arr[j]>arr[j+1])
           f=1;
      if(f==1)
      System.out.println("false");
           else
           System.out.println("true");
    }
}

排列顺序/顺序分析

Arranging sequence / Sequence Analysis

java

arrays

sequence

analysis