|
1.将数组中的大写字母与小写字母分开
例子：一个数组中存储有且仅有大写和小写字母，编写一个函数对数组内的字母重新排列，让小写字母在大写字母之前
#include<iostream>
#include<string>
using namespace std;
//判断是否为大写字母
bool isUpper(char a){
if(a>='A' && a<='Z')
return true;
return false;
}
//判断是否为小写字母
bool isLower(char a){
if(a>='a' && a<='z')
return true;
return false;
}
void partition(string &str, int low, int high){
while(low<high){
while(low<high && isUpper(str[high])) high--;
while(low<high && isLower(str[low])) low++;
char temp=str[high];
str[high]=str[low];
str[low]=temp;
}
}
int main(){
string str;
cin>>str;
int len=str.length();
partition(str,0,len-1);
for(int i=0; i<len; i++)
cout<<str[i]<<" ";
return 0;
}
2.给定含有n个元素的整型数组a,其中包括0元素和非0元素，对数组进行排序，
要求：
排序后所有0元素在前，所有非0元素在后，且非0元素排序前后相对位置不变；
不能使用额外的空间
例如：
输入：0 3 0 2 1 0 0
输出：0 0 0 0 3 2 1
#include<iostream>
using namespace std;
void partition(int a[],int low, int high){
int i=high+1;
for(int j=high; j>=low; j--){
if(a[j]!=0){
i--;
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
int main(){
int a[7]={0,3,0,2,1,0,0};
partition(a,0,6);
for(int i=0; i<7;i++){
cout<<a[i]<<" ";
}
return 0;
}
3.进阶-荷兰国旗问题
将乱序的红白蓝三色小球排列成同颜色在一起的小球组（按照红白蓝排序），这个问题成为荷兰国旗问题。这是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗，如下面所示，0表示红球，2表示蓝球，1表示白球
这个问题类似于快排中partition过程。不过，要用指针，一前begin，一中current，以后end，begin与current都初始化指向数组首部，end指向数组尾部。
1）.current遍历整个数组序列，current指向1时，不交换，current++
2）.current指向0时，与begin交换，而后current++，begin++
3）.current指向2时，与end交换，而后currentcurrent不动，end--
#include<iostream>
using namespace std;
void partition(int *num, int n){
int begin=0,current=0,end=n-1;
while(current<=end){
if(num[current]==0){
int temp=num[current];
num[current]=num[begin];
num[begin]=temp;
current++;
begin++;
}
else if(num[current]==1)
current++;
else{
int temp=num[current];
num[current]=num[end];
num[end]=temp;
end--;
}
}
}
int main(){
int num[10]={0,1,2,1,1,2,0,2,1,0};
partition(num,10);
for(int i=0;i<10;i++){
cout<<num[i]<<" ";
}
return 0;
}
4.最小的k个数
#include<iostream>
using namespace std;
int Partition(int *num,int low,int high){
int pivot=num[low];
while(low<high){
while(low<high && num[high]>=pivot)
high--;
num[low]=num[high];
while(low<high && num[low]<=pivot)
low++;
num[high]=num[low];
}
num[low]=pivot;
return low;
}
void getLeastKNum(int *input, int n,int k){
if(input == NULL || k>n || n<=0 || k<=0)
return;
int start=0;
int end=n-1;
int index = Partition(input,start,end);
while(index !=k-1){
if(index >(k-1)){
end=index-1;
index=Partition(input,start,end);
}
else{
start=index+1;
index=Partition(input,start,end);
}
}
for(int i=0; i<k; i++){
cout<<input[i]<<" ";
}
}
int main(){
int input[8]={8,231,2,24,5,34,12,9};
getLeastKNum(input,8,5);
return 0;
}
| 
转播
