目录
数组中有一个数字出现的次数超过了数组长度的一半，请找到这个数字。
例如：输入数组{1，2，3，2，2，2，5，4，2}，由于数字2在数组中出现了5次，超过了数组长度的一半，输出2，如果不存在则输出0。
先对数组进行排序，在一个有序数组中次数超过一般的就是中位数，可以再次遍历数组确认这个数字出现的次数是否超过一半。
首先HashMap中key就是数组中的元素，value是元素出现的次数，遍历数组统计所有元素出现的次数。最后再遍历Hash，超导次数超过一半的数字。
public static int moreThanHalfNum_My(int[] array) {
if (array == null){
return 0;
}
Map<Integer,Integer> res=new HashMap<>();
int length=array.length;
for (int i = 0; i < array.length; i++) {
/*Map.getOrDefault(Object key, V defaultValue);
如果在Map中存在key，则返回key所对应的的value。
如果在Map中不存在key，则返回默认值。*/
res.put(array[i],res.getOrDefault(array[i],0)+1);
if (res.get(array[i]) > length/2){
return array[i];
}
}
return 0;
}给你一个?非空?整数数组?nums?，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 ：
输入：nums = [2,2,1]
输出：1可以利用Set集合不存重复值的特性，当存入相同的元素时，不再进行添加，同时将已存在的那个元素一起删除，最后只留下那个只出现了一次的数字。
public static int singleNumber(int[] nums) {
Set<Integer> set=new HashSet<>();
for (int i : nums) {
if (!set.add(i)){
set.remove(i);
}
}
if (set.size()==0){
return 0;
}
return set.toArray(new Integer[set.size()])[0];
}利用异或的规则，如0^0=0; 0^1=1; 1^1=0;?
0与其他数字数字异或结果还是那个数字，要操作的数字中除了某个数字只出现了一次之外，其他数字都出现了两次，所以可以定义一个变量初始为0，用这个数字与数组中的每个数字做异或运算，并将这个变量值更新为那个运算结果，直到数组遍历完成，最后得到的值就是数组中只出现了一次的数字。
public static int singleNumber_2(int[] nums) {
int flag=0;
for (int i : nums) {
flag^=i;
}
return flag;
}给定一个包含红色、白色和蓝色、共?n?个元素的数组?nums?，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数?0、?1?和?2?分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 ：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]利用两次遍历将所以的0移到左边，第二次将所有的2移到右边即可
public static void sortColors(int[] nums) {
int n = nums.length;
int left = 0;
//将所有的0交换到数组的最前面
for (int right = 0; right < n; right++) {
if (nums[right] == 0) {
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
left++;
}
}
//将所有的1交换到2的前面
for (int right = left; right < n; ++right) {
if (nums[right] == 1) {
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
++left;
}
}
}利用左右双指针和当前元素的指针，将当前元素和左右两边的元素调换位置，也只需要考虑0和2的情况，当当前元素为0时，将当前指针指向的元素和左边元素互换位置，同时两个指针都加一向右移；当当前元素为2时，将当前指针指向的元素和右边元素互换位置，此时因为不知到右边元素是0还是1，所以只需要将右边的指针减一向左移即可。
public static void sortColors_My(int[] nums) {
int left=0;
int right=nums.length-1;
int index=0;
while (index<=right){
if (nums[index]==0){
swap(nums,left++,index++);
}else if (nums[index]==2) {
swap(nums,right--,index);
}else index++;
}
}
public static void swap(int[] nums,int m,int n){
int temp=nums[m];
nums[m]=nums[n];
nums[n]=temp;
}