给定一个个数字arr,判断数组arr中是否所有的数字都只出现过一次。
输入包括两行,第一行一个整数n,代表数组arr的长度。第二行包括n个整数,代表数组arr。
如果arr中所有数字都只出现一次,输出“YES”,否则输出“NO”。
3 1 2 3
YES
3 1 2 1
NO
要求1.时间复杂度。2.额外空间复杂度。
/*时间 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; }
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")
要控制额外空间复杂度为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
复杂度的循环”,但构建二叉堆是自下而上的构建,每一层的最大纵深总是小于等于树的深度的,因此,时间复杂度计算是叠加的。
#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; }
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; } }
#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; }