11225: 【原1225】distinct

题目

题目描述

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

Description

P322.1

Input Format

第一行读入一个整数 N

第二行读入 N 个整数， 构成数组A

Output Format

输出一个整数，表示数组A中不同的数的个数

解释： 比如 1 2 2 3 3 4 就有4种不同的数分别是1 2 3 4

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;
}