判断数组中每个数是否只出现一次

1.hash表

2.空间复杂度规定O(1)，怎么是时间复杂度尽可能低

排序，然后从下标1开始判断该数是否和左边数相等

3.排序算法shijian复杂度

O(n）桶排序，基数排序 O(nlogn)快排（空间复杂度O(logn)，logn的空间来记录轴元素位置，partition之后才知道轴元素放哪里）,堆排（空间O(1)）,归并(空间O（n）),希尔(成败取决于步长)

堆排序如果用递归则空间复杂度为O(nlogn),非递归版本为O(1)

4.在数组中判断是否有一个数出现次数大于一半（水王问题）如果存在只能是一个

是否有一个数出现次数大于n/k次k为系统给定 要准备k-1个候选