首页 > 试题广场 >

判断数组中所有的数字是否只出现一次

[编程题]判断数组中所有的数字是否只出现一次

热度指数：1486 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个个数字arr，判断数组arr中是否所有的数字都只出现过一次。

输入描述:

输入包括两行，第一行一个整数n，代表数组arr的长度。第二行包括n个整数，代表数组arr。

输出描述:

如果arr中所有数字都只出现一次，输出“YES”，否则输出“NO”。

示例1

输入

3
1 2 3

输出

YES

示例2

输入

3
1 2 1

输出

NO

备注:

要求
1.时间复杂度。
2.额外空间复杂度。

算法知识视频讲解

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>m;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
        m[arr[i]]++;
    }
    for(auto i:m)
    {
        if(i.second>1)
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

发表于 2019-09-14 14:46:44 回复(0)

helloxuanbao

/*时间 O(NlogN) 额外空间 O(1) */

#include <stdio.h>

void swap(int *arr, int i, int j);

void downAdjust(int *arr, int i, int n);

int main(void) {
    int n, *arr, size;
    scanf("%d", &n);
    arr = (int *) malloc(sizeof(int) * n);
    size = n;
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    for (int i = (n - 1) >> 1; i >= 0; i--) {
        downAdjust(arr, i, size);
    }
    while (size > 1) {
        swap(arr, 0, size - 1);
        downAdjust(arr, 0, size - 1);
        size--;
    }
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

void swap(int *arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

void downAdjust(int *arr, int i, int n) {
    int left = i << 1 | 1, bigger;
    while (left < n) {
        bigger = left + 1 < n && arr[left + 1] > arr[left] ?
            left + 1 : left;
        if (arr[i] >= arr[bigger]) {
            break;
        }
        swap(arr, i, bigger);
        i = bigger;
        left = i << 1 | 1;
    }
}

// 时间 O(N) 额外空间 O(N)
#include <cstdio>
#include <unordered_set>

using namespace std;

int main() {
    int n, cur;
    unordered_set<int> iset;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &cur);
        if (iset.find(cur) != iset.end()) {
            printf("NO\n");
            return 0;
        }
        iset.insert(cur);
    }
    printf("YES\n");
    return 0;
}

发表于 2022-02-06 15:41:07 回复(0)

pein531

使用默认字典计数，当键的个数与所有值的和均为n时满足要求

from collections import defaultdict

counter = defaultdict(lambda : 0)
n = int(input())
nums = list(map(int, input().split()))
for num in nums:
    counter[num] += 1
if len(counter) == n and sum(counter.values()):
    print("YES")
else:
    print("NO")

发表于 2021-06-25 23:38:54 回复(0)

Java

jahentao

要控制额外空间复杂度为O(1)，几种O(NlogN)的排序算法中，只有堆排序满足。

本题只需要在堆排序的建堆过程中进行判断，而建堆的时间复杂度是O(N)。

import java.util.*;
public class Main {
    public static boolean heapInsert(int[] arr, int i) {
        while (i != 0) {
            int parent = (i - 1)/2;
            if (arr[parent] < arr[i]) {
                int tmp = arr[parent];
                arr[parent] = arr[i];
                arr[i] = tmp;
                i = parent;
            } else if (arr[parent] == arr[i]){
                return false;
            } else {
                break;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (!heapInsert(arr, i)) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}

PS: 关于计算建堆的时间复杂度，虽然算法外层是一个N次循环，而内层看起来像“一个的logN复杂度的循环”，但构建二叉堆是自下而上的构建，每一层的最大纵深总是小于等于树的深度的，因此，时间复杂度计算是叠加的。

编辑于 2020-05-20 08:48:22 回复(5)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x;
    scanf("%d", &n);
    unordered_map<int, bool> M;
    bool flag = true;
    while(n--){
        scanf("%d", &x);
        if(flag){
            if(M.find(x)!=M.end())
                flag = false;
            else
                M[x] = true;
        }
    }
    printf("%s\n", flag?"YES":"NO");
    return 0;
}

发表于 2020-04-25 00:51:30 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        if(isUnique(arr)==0){
            System.out.print("YES");
        }else{
            System.out.print("NO");
        }
        
    }
    public static int isUnique(int[] arr){
        if(arr==null){
            return 0;
        }
        int res=0;
        for(int i=1;i<arr.length;i++){
            if(arr[i]-arr[i-1]==0){
                res++;
            }
        }
        return res;
    }
}

发表于 2021-03-30 14:45:30 回复(0)

C/C++

codewind

#include<cstdio>
#include<unordered_set>
int main() {
    int n;
    scanf("%d", &n);
    int x;
    std::unordered_set<int> _set;
    for(int i=0;i<n;++i) {
        scanf("%d", &x);
        if(_set.count(x)) {
            puts("NO");
            return 0;
        }
        _set.insert(x);
        
    }
    puts("YES");
    return 0;
}

发表于 2021-02-02 21:46:20 回复(0)

牛客755659385号

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.nextLine());
String[] arr = sc.nextLine().split(" ");
Set<String> set = new HashSet<>();
for (int i = 0; i < n; i++) {
            if (!set.add(arr[i])) {
                System.out.println("NO");
                return;
            }
        }
System.out.println("YES");
}
}

发表于 2020-05-17 22:37:30 回复(0)

C/C++

Jiangzc

万物皆可排序

#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;

void check(vector<int>v)
{
    for (int j = 0; j < v.size() - 1; j++)
    {
        if (v[j] == v[j + 1])
        {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}
int main()
{
    int t;
    int num;
    cin >> t;
    vector<int> v;
    for (int i = 0; i < t; i++)
    {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(),v.end());
    check(v);
    return 0;
}

发表于 2020-04-02 12:54:36 回复(0)