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

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

要控制额外空间复杂度为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复杂度的循环”，但构建二叉堆是自下而上的构建，每一层的最大纵深总是小于等于树的深度的，因此，时间复杂度计算是叠加的。