快排的partition算法解题
2016-09-19 本文已影响0人
AlwaysFrank
-
最小的k个数，输入n个整数，找出其中最小的k个数
可以建立大小为K的小顶堆。
也可以运用partition函数进行求解，不过我们完整的快速排序分割后要递归地对前后两段继续进行分割，而这里我们需要做的是判定分割的位置，然后再确定对前段还是后段进行分割，所以只对单侧分割即可。
#include <iostream>
#define N 10
#define K 4
using namespace std;
//使用引用，完成两数交换
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//快排的partition算法，这里的基准数是随机选取的
template <typename T>
int Partition(T* data,int length, int low, int high)
{
if(low<high)
{
int key = data[low];
int i = low;
for(int j=low+1; j<=high; j++)
{
if(data[j]<=key)
{
i = i+1;
Swap(data[i], data[j]);
}
}
Swap(data[i],data[low]);
return i;
}
else
{
return low;
}
}
//最小的K个元素
template <typename T>
void GetLeastNumbers_by_partition(T* input, int n, T* output, int k)
{
if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
{
return;
}
int start = 0;
int end = n - 1;
int index = Partition(input, n, start, end);
while(index != k - 1)
{
if(index > k - 1)
{
end = index - 1;
index = Partition(input, n, start, end);
}
else
{
start = index + 1;
index = Partition(input, n, start, end);
}
}
for(int i = 0; i < k; ++i)
output[i] = input[i];
}
//输出
template <typename T>
void displayArray(T &myArray)
{
for (auto m :myArray)
{
cout<<m<<" ";
}
}
int main()
{
int arrayInt[] = {4,5,1,6,2,7,3,8,1,2};
int arrayIntResult[K];
//输出初始化结果
cout<<"原始数组"<<endl;
displayArray(arrayInt);
cout<<endl;
//最小的4个元素
GetLeastNumbers_by_partition(arrayInt,N,arrayIntResult,4);
cout<<"最小的"<<K<<"个元素"<<endl;
displayArray(arrayIntResult);
cout<<endl;
return 0;
}
- 判断数组中出现超过一半的数字
#include <iostream>
using namespace std;
//使用引用，完成两数交换
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//快排的partition算法，这里的基准数是随机选取的
template <typename T>
int Partition(T* data,int length, int low, int high)
{
if(low<high)
{
int key = data[low];
int i = low;
for(int j=low+1; j<=high; j++)
{
if(data[j]<=key)
{
i = i+1;
Swap(data[i], data[j]);
}
}
Swap(data[i],data[low]);
return i;
}
else
{
return low;
}
}
bool g_bInputInvalid = false;
template <typename T>
bool CheckInvalidArray(T* numbers, int length)
{
g_bInputInvalid = false;
if(numbers == NULL && length <= 0)
g_bInputInvalid = true;
return g_bInputInvalid;
}
template <typename T>
bool CheckMoreThanHalf(T* numbers, int length, int number)
{
int times = 0;
for(int i = 0; i < length; ++i)
{
if(numbers[i] == number)
times++;
}
bool isMoreThanHalf = true;
if(times * 2 <= length)
{
g_bInputInvalid = true;
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
template <typename T>
int MoreThanHalfNum_Solution(T* numbers, int length)
{
if(CheckInvalidArray(numbers, length))
return 0;
int middle = length >> 1;
int start = 0;
int end = length - 1;
int index = Partition(numbers, length, start, end);
while(index != middle)
{
if(index > middle)
{
end = index - 1;
index = Partition(numbers, length, start, end);
}
else
{
start = index + 1;
index = Partition(numbers, length, start, end);
}
}
int result = numbers[middle];
if(!CheckMoreThanHalf(numbers, length, result))
result = 0;
return result;
}
//输出
template <typename T>
void displayArray(T &myArray)
{
for (auto m :myArray)
{
cout<<m<<" ";
}
}
int main()
{
int arrayInt[] = {4,5,1,6,6,6,6,6,6,6,6,6,6,2,7,3,8,1,2};
//输出初始化结果
cout<<"原始数组"<<endl;
displayArray(arrayInt);
cout<<endl;
int length = sizeof(arrayInt)/sizeof(int);
//超过一半的数字
cout<<"超过一半的数字: ";
cout<<MoreThanHalfNum_Solution(arrayInt,length);
cout<<endl;
//另解 排序后在中间的数字，统计次数如果大于一半即为所求
cout<<"超过一半的数字: ";
cout<< arrayInt[length/2];
cout<<endl;
return 0;
}
- 有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面(不要求保持原顺序)
若要求保持原序列，可用冒泡的思想来求解！！！
#include <iostream>
using namespace std;
void Process( char *str )
{
int i = 0;
int j = 0;
//移动指针i, 使其指向第一个大写字母
while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;
if( str[i] != '\0' )
{
//指针j遍历未处理的部分，找到第一个小写字母
for( j=i; str[j] != '\0'; j++ )
{
if( str[j] >= 'a' && str[j] <= 'z' )
{
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
i++;
}
}
}
}
int main()
{
char data[] = "HelloWorld";
cout<<"Before : "<<data<<endl;
Process( data );
cout<<"After : "<<data;
return 0;
}
