stl 中 next_permutation、prev_permutation的原理和使用

next_permutation实现原理
在《STL源码解析》中找到了这个函数,在此也简单叙述一下原理:
在STL中,除了next_permutation外,还有一个函数prev_permutation,两者都是用来计算排列组合的函数。前者是求出下一个排列组合,而后者是求出上一个排列组合。所谓“下一个”和“上一个”,书中举了一个简单的例子:对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
next_permutation的函数原型如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
 );

对于第二个重载函数的第三个参数,默认比较顺序为小于。如果找到下一个序列,则返回真,否则返回假。
函数实现原理如下:
在当前序列中,从尾端往前寻找两个相邻元素,前一个记为*i,后一个记为*ii,并且满足*i < *ii。然后再从尾端寻找另一个元素*j,如果满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包括ii)的所有元素颠倒排序,即求出下一个序列了。
代码实现如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator first,
      BidirectionalIterator last
)
{
    if(first == last)
        return false; //空序列
    BidirectionalIterator i = first;
    ++i;
    if(i == last)
        return false;  //一个元素,没有下一个序列了
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i;
        --i;
        if(*i < *ii) {
            BidirectionalIterator j = lase;
            while(!(*i < *--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if(i == first) {
            reverse(first, last);  //全逆向,即为最小字典序列,如cba变为abc
            return false;
        }
    }
}

prev_permutation实现类似,就是反向查找。
例子:

#include<iostream>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	    string str = "abcd";
	    do{
		        cout<<str<<endl;
    	}while(next_permutation(str.begin(), str.end()));
	    cout<<"after loop:\n"<<str<<endl;
    	return 0;
}

输出:

[zhangjun@s3 leetcode]$ ./strtest
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
after loop:
abcd

 
最后一个排列没有下一个排列,用next_permutation会返回false,但使用这个方法后,序列会变成字典序列的第一个。如dcba变成abcd。

数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。
解法:由于数组是有序的,可以采用二分查找的思想,分别查找连续k值得左边界和有边界,
class Solution {
public:
    int GetStartOfK(vector<int> data, int k){  // 查找左边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size()-1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] >= k)        // 大于等于k时,end向start紧靠,找到左边界
                end = mid - 1;
            else
                start = mid + 1;
        }
        if(data[start] == k)
            return start;
        else
            return -1;
    }
    int GetEndOfK(vector<int> data, int k){  //查找右边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size() - 1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] <= k)         // 小于等于k时, start向end紧靠,找到右边界
                start = mid + 1;
            else
                end = mid - 1;
        }
        if(data[end] == k)
            return end;
        else
            return -1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() > 0){
            int start = GetStartOfK(data, k);
            int end = GetEndOfK(data, k);
            if(start > -1 && end > -1)
                count = end - start + 1;
        }
        return count;
    }
};

 

Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};