题解 | #明明的随机数#
明明的随机数
http://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0
C++实现，不借助容器，先排序，后去重，排序是递归实现快速排序，去重要考虑到重复两个以上的情况。代码如下：
#include<iostream>
using namespace std;
int GetIndex(int arr[],int low,int high);
void QuickSort(int arr[],int low,int high); //快速排序
void DeleteRepeated(int arr[],int* num); //去重
int main()
{
int arr[1000]={0};
int num=0;
while(cin>>num)
{
arr[1000]={0};
for(int i=0;i<num;++i)
{
cin>>arr[i];
}
QuickSort(arr, 0, num-1);
DeleteRepeated(arr, &num);
for(int i=0;i<num;++i)
{
cout<<arr[i]<<endl;
}
}
return 0;
}
int GetIndex(int arr[],int low,int high)
{
int temp;
int pivot=low;
while(low!=high)
{
if(arr[high]>arr[pivot])
--high;
else
{
if(arr[low]<=arr[pivot])
++low;
else
{
temp=arr[low];
arr[low]=arr[high];
arr[high]=temp;
--high;
}
}
}
temp=arr[low];
arr[low]=arr[pivot];
arr[pivot]=temp;
return low;
}
void QuickSort(int arr[],int low,int high)
{
if(low>=high) return;
int index=GetIndex(arr, low, high);
QuickSort(arr, low, index-1);
QuickSort(arr, index+1,high);
}
void DeleteRepeated(int arr[],int* num)
{
for(int i=0;i<*num;++i)
{
if(arr[i]==arr[i+1])
{
for(int j=i;j<*num;++j)
{
arr[j]=arr[j+1];
}
(*num)--;
i--;
}
else continue;
}
} 
