脸/非死不可 电2020面筋

xxxxqia 发表于 2020-10-26 08:41
感谢楼主，第二题只做过类似的next permutation. 以为一样的，结果有 [3，1，1，3] 这种corner case，关键 ...

是啊，这个题目真的，作为面试题真会把人烦死，而且当时小哥就说了句"you know what is prev permutation right?"

我觉得这个题目的难点在于理解这个规律，光是这个就要花很多时间，更别说还要在这么短的时间内写出来了，目测是跪定了

请问多久出的结果呀

wutingmin 发表于 2020-10-30 08:22
请问多久出的结果呀

3天之后出的结果，然后居然过了

anastasia22 发表于 2020-10-29 17:41:31
3天之后出的结果，然后居然过了

恭喜哈，看来我得等几天了

其实 我觉得1313 这个 不算是corner case 呀 。

其实这道题的核心思想是，怎么样可以变小，但是变得没那么小。所以这就决定了你做交换的时候保证1. 尽量对高位的数字不要有影响 2. 对有影响的低位数字消减的最小。


比如 [1,9,4,6,7]，我们的思路应该是从后往前搜索，比如我在 6 这个位置，我一定是要向后搜索，找一个比6小，但是在比6小的情况下最大的那个，相当于 矮子里面挑高个，这样才可以保证

1. 换了 6之后对前面高位的数字没有影响
2. 交换之后的低位数字是我能凑到的最大的数字

满足这两点就可以保证得到的数组组成的数字一定是比原来的小，但是是小的里面最大的那个。当然在这个6 的例子里面是没有找到合适的交换数字。
但是换成9的话就不一样了，明显在后面有4，6，7比9小，但是明显7最大，那理所应当就是9和7交换变成 [1,7,4,6,9]

基于以上两点一个O(N^2) 的解法是

1. public int[] prevPermOpt1(int[] A) {
   
2.         if (A.length == 1 || A.length == 0) {
   
3.             return A;
   
4.         } else {            //从后往前搜索哦
   
5.             for (int i = A.length-1; i >= 0; i--) {
   
6.                // 比当前小，但是是小的里面最大的那个value
   
7.                 int tempMax = -1;
   
8.                //value 的index，方便我之后交换
   
9.                 int index = -1;
   
10.                 for (int j = A.length-1; j > i; j--) {
    
11.                     //第二重循环，找i之后的数字，如果比i指向的小，而且比当前以及得到的最大值还要大，这个就是合适的candidate
    
12.                     if (A[j] < A[i] && A[j] >= tempMax) {
    
13.                         tempMax = A[j];
    
14.                         index =  j;
    
15.                     }
    
16.                 }[/i]
    
17. [i]                 //只要找到了一个合适的，这个肯定是最终答案，
    
18.                 if (tempMax != -1) {
    
19.                     swap(i, index ,  A);
    
20.                     return A;
    
21.                 }
    
22.             }
    
23.             return A;
    
24.         }
    
25.     }
    
26. 
    
27.     private void swap(int i, int j, int[] A) {
    
28.         int temp = A[i];
    
29.         A[i] = A[j];
    
30.         A[j] = temp;
    
31.     }

复制代码

所以 3113 也是同样思路。 你在最后一个3的时候，后面没有数字可以交换 ，忽略它。两个1后面都没有比他小的，忽略。到第一个3的时候，你从后找，找到一个1比他小，而且1是能找到比第一个3小的最大值了。交换就得出 1313

这个是AC答案而且速度是100%。我暂时没想到O(N)的解法，不过关键在于怎么快速找到比当前index的数字小，但是是小的里面最大的这样一个数据结构。[/i][/i][/i]

儒雅随和的小川 发表于 2020-10-24 10:03
这道题3113正确是1313我是真想了半小时，遇到了我也不知道怎么解释，下周面试估计纯看命

小川同学我提供了点思路，您可以参考一下，希望可以帮到你~