拼多多笔试，第一题非严格递增数组排序，求解

import java.util.Arrays; import java.util.Scanner; public class Main1 { private static int index = 0; private static int replaceNum; private static int[] A; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] arr1 = sc.nextLine().split(" "); String[] arr2 = sc.nextLine().split(" "); if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0) { System.out.print("NO"); return; } A = new int[arr1.length]; int[] B = new int[arr2.length]; int i = 0; for (String s : arr1) { A[i++] = Integer.parseInt(s); } i = 0; for (String s : arr2) { B[i++] = Integer.parseInt(s); } findInA(A); Arrays.sort(B); if(findInB(B, index)) { //替换index的值 只能AC70% A[index] = replaceNum; } else if (findInB(B, index - 1)) { //考虑替换index-1的值 A[index - 1] = replaceNum; } if (isSorted(A)) { printArray(A); } else { System.out.print("NO"); } sc.close(); return; } private static void printArray(int[] a) { for (int i = 0; i < a.length; i++) { if (i != a.length - 1) System.out.print(a[i] + " "); else System.out.print(a[i]); } } private static boolean isSorted(int[] newA) { for (int i = 1; i < newA.length; i++) { if (newA[i] <= newA[i - 1]) { return false; } } return true; } private static boolean findInB(int[] b, int index) { int res = Integer.MIN_VALUE; for (int num : b) { if (index >= 1) { if (num > A[index - 1] && num < A[index + 1]) { res = Math.max(res, num); } } else if (index == 0) { if (num < A[index + 1]) { res = Math.max(res, num); } } } boolean result = res == Integer.MIN_VALUE ? false : true; if (result) { replaceNum = res; } return result; } private static void findInA(int[] a) { for (int i = 1; i < a.length; i++) { if (a[i - 1] >= a[i]) { index = i; } } } }

int main() {     vector<int> a;     a.push_back(0x80000000);     vector<int> b;     char c;     int num;     while ((c = getchar()) != '\n')     {         if (c != ' ')         {             ungetc(c, stdin);             cin >> num;             a.push_back(num);         }     }     a.push_back(0x7FFFFFFF);     while ((c = getchar()) != '\n')     {         if (c != ' ')         {             ungetc(c, stdin);             cin >> num;             b.push_back(num);         }     }     int index = 0;     for (int i = a.size()-1; i>0; i--)     {         if (a[i] <= a[i - 1] && a[i] <= a[i + 1])         {             index = i;             break;         }     }     int max = 0x80000000;     //在b中查找     for (int i = 0; i < b.size(); i++)     {         if (b[i] > a[index-1]&&b[i]<a[index+1]&&b[i]>max)             max = b[i];     }     if (max == 0x80000000)         cout << "NO" << endl;     else     {         a[index] = max;         for (int i = 1; i < a.size()-1; i++)             cout << a[i] << " ";     }     return 0; }

我是设max初始为Integer.MAX_Value，min为Integer.MIN_Value，找到a[i]>=a[i+1]的位置，然后如果i>0那么min=a[i-1]，如果i+2<数组length那么max=a[i+2]。然后b从大到小遍历，找出一个数大于a[i]且小于max，或者大于min且小于a[i+1]。

你的index就错了，leetcode上有个类似的题，替换位置有两种情况，应该维护两个备选位置，写起来比较复杂

感觉思路很好想，但是***写的太暴力 TLE 了。。 可能因为我每次用一个数替换index或者index+1之后我都遍历一遍a数组（n个）判断数组的严格升序了？也就是O(2*MN)太慢了?

还需要选的数是最大啊

mark

我没考虑替换index为啥能过70%。。。