# 11225: 【原1225】distinct

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1225

P322.1

## Sample Input

``````10
1 3 3 4 2 2 4 1 1 5
``````

## Sample Output

``````5
``````

## Tips

1.时间复杂度必须是O(NlogN)：利用快速排序预处理

2.题目中的N可能比较大，数组尽量开到1M的数量级

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/12.
//

#ifndef SBL_BQSORT_H
#define SBL_BQSORT_H

template<typename Item>
class BQSort {
private:
static bool less(Item v, Item w) {
return v < w;
}

static void exch(Item *a, int i, int j) {
Item t = a[i];
a[i] = a[j];
a[j] = t;
}

public:
static void sort(Item *a, int n) {
sort(a, 0, n - 1);
}

static void sort(Item *a, int lo, int hi) {
if (hi <= lo) return;
int mid = partition(a, lo, hi);
sort(a, lo, mid - 1);
sort(a, mid + 1, hi);
}

static int partition(Item *a, int lo, int hi) {
int i = lo, j = hi + 1;
Item v = a[lo];
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
};

#endif //SBL_BQSORT_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
auto a = new int[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
BQSort<int>::sort(a, n);

int index = 1;
int last = a[0];
int ans = 1;
for (; index < n; ++index) {
if (a[index] != last) {
++ans;
last = a[index];
}
}
cout << ans << endl;
delete[] a;
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
int n; int a[1000050];
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a + n);
int cnt = 1;
for (int i = 1; i < n; ++i)
if (a[i] != a[i - 1]) ++cnt;
printf("%d\n", cnt);
return 0;
}
``````

## Zsi-r's solution

``````#include <iostream>

using namespace std;

int divide(int array[],int low,int high)
{
int temp = array[low];
do{
while(low<high&&array[high]>=temp)high--;
if (low<high) array[low++] = array[high];
while(low<high&&array[low]<=temp)low++;
if(low<high) array[high--]=array[low];
}while(low!=high);
array[low] = temp;
return low;
}

void quicksort(int array[],int low,int high)
{
int mid;
if (low>=high) return ;
mid = divide(array,low,high);
quicksort(array,low,mid-1);
quicksort(array,mid+1,high);
}

void quicksort(int array[],int size)
{
quicksort(array,0,size-1);
}

int main()
{
int num,i,appeared,access_now,count=0;
cin>> num;
int *array = new int [num];
for (i=0;i<num;i++)
{
cin >> array[i];
}
quicksort(array,num);
appeared=array[0]-1;//let appeared and access_now be defferent initialy
for (i=0;i<num;i++)
{
access_now = array[i];
if (access_now==appeared)
continue;
else
{
count++;
appeared = access_now;
}
}
cout << count;
return 0;
}
``````