题解 | #下一个排列#

下一个排列

http://www.nowcoder.com/practice/50b0b87e50be4944b34cb0f2ce618197

题意

求数组的所有排列中,恰好在当前数组排列的下一个的数组

限制:

数组长度不大于1000

方法

性质分析

如果一个数组恰好是另一个数组排列的下一个,那么首先两个数组不等,其次它们有公共前缀,在公共前缀后新数组比原数组大, 新数组剩余部分从小到大排列

正确性证明:

因为是下一个,所以不相等.存在一位下一个更大

因为满足前缀相等,后一位更大的中,最小的是剩余部分从小到大排列的, 因此这样的最小的就是排列的下一个

以题目样例[1,2,3]为例

固定位	更大位	顺序位	最终结果
""	[2]	[1,3]	[2,1,3]
[1]	[3]	[2]	[1,3,2]
[1,2]	不存在更大位	-	-

而其中最小的是[1,3,2]

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextPermutation(vector<int>& nums) {
        // write code here
        vector<int> off; // 后缀数字
        for(int i = nums.size()-1;i>=0;i--){ // 在后缀数字中找比nums[i]大的中的最小的
            int posj = -1;
            for(int j = 0;j<off.size();j++){
                if(off[j] > nums[i] && (posj == -1 || off[j] < off[posj])) posj = j; // 找到最小的
            }
            // [0...i-1] off[posj] sort([i..n]/nums[posj])
            if(posj != -1){
                vector<int> res = {};
                for(int k=0;k<i;k++) res.push_back(nums[k]); // [0..i-1]
                res.push_back(off[posj]); // posj
                off[posj] = nums[i];
                sort(off.begin(),off.end()); // 从小到大
                for(int k = 0;k < off.size() ;k++) res.push_back(off[k]);
                return res;
            }
            off.push_back(nums[i]); // 加入后缀数组
        }
        // 全部从大到小
        sort(off.begin(),off.end());
        return off;
    }
};

复杂度分析

时间复杂度: 对于每个位置会搜索后缀数组中是否有比它大的,所以时间复杂度为 $O(n^2 + n\cdot log(n))$

空间复杂度: 空间主要在结果记录,空间复杂度为 $O (n)$

查询优化

注意到上面每次我们去数组中找最小的且大于当前值的值.

然而我们可以维护一个小根堆,随时准备输出,同时记录最大值,来查询当前堆中是否有大于当前值的存在

这样, 判断效率变为了 $O (1)$ ,而合并和查询的效率在总的就只有 $O(n \cdot log(n))$

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextPermutation(vector<int>& nums) {
        multiset<int> inc; // 升序 后缀数字
        int maxv = 0;
        for(int i = nums.size()-1;i>=0;i--){ // 在后缀数字中找比nums[i]大的中的最小的
            if(maxv > nums[i]){
                vector<int> res = {};
                for(int k=0;k<i;k++) res.push_back(nums[k]); // [0..i-1]
                res.push_back(0); // 占位
                bool found = false; // 是否找到了比当前数大的
                for(auto item:inc){ // 递增输出
                    if(!found && item > nums[i]){ // 首次找到,是比当前数大的最小的数
                        found = true;
                        res[i] = item; // 替换占位
                        res.push_back(nums[i]);
                    }else{
                        res.push_back(item);
                    }
                }
                return res;
            }
            inc.insert(nums[i]);
            maxv = max(maxv,nums[i]);
        }
        // 全部从大到小
        sort(nums.begin(),nums.end());
        return nums;
    }
};