教做潮男的网站/什么网站可以免费推广

1. 思路分析

堆排序，然后取length/2下标位置的值。或者使用投票法，依次遍历数组元素，一样就+1，否则-1。如果=0，换人投票。具体看代码

2. 代码
   

class Solution {/**Boyer-Moore算法O(n)  O(1)[2,2,1,1,1,2,2]candidate 为 当前找的众数count 为数量，如果count = 0，就将当前遍历的数作为candidate假设第一次candidate 为2 count = 1[2,2,1,1,1,2,2]candidate    2 count        1 第二次，先判断count == 0，不相等，就继续用candidate比较，如果一致就count++，否则--[2,2,1,1,1,2,2]candidate    2 2count        1 2第三次，重复步骤，count!=0,继续用candidate比较，此时candidate与数组元素1不一致，count--[2,2,1,1,1,2,2]candidate    2 2 2count        1 2 1第四次，又不一样，--[2,2,1,1,1,2,2]candidate    2 2 2 2count        1 2 1 0第五次，count == 0，那么candidate就变为当前元素值1.然后再比较[2,2,1,1,1,2,2]candidate    2 2 2 2 1count        1 2 1 0 1第六次，count！=0，但是candidate不一致，count--[2,2,1,1,1,2,2]candidate    2 2 2 2 1 1count        1 2 1 0 1 0第七次，count == 0. candidate需要变化为2，然后再比较，count++[2,2,1,1,1,2,2]candidate    2 2 2 2 1 1 2count        1 2 1 0 1 0 1遍历完成，candidate保存的就是众数*/public int majorityElement(int[] nums) {// int count = 0;//初始为0// Integer candidate = null; //candidate初始为null// for(int num : nums){//依次遍历//     if(count == 0) candidate = num;//先判断count == 0 ，等于0，candidate就要等于当前num//     count += (num==candidate)?1:-1;//如果一致就count++，否则count--// }// return candidate;//最终candidate保存的就是目标值//下面这样写，LeetCode执行用时更少，但实际上一毛一样。int count=0,candidate=(int)2e9;for(int i=0;i<nums.length;i++){if(count==0){candidate=nums[i];}if(candidate==nums[i]){count++;}else{count--;}}return candidate;}/**先排序，Arrays.sort(nums)使用timsort排序算法，最坏情况O(n log n)空间复杂度最坏情况是O(log n ) 最好情况是O(1)如果自己写堆排序的话，空间复杂度是O(1)*/public int majorityElement1(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}/**使用堆排序*/public int majorityElement2(int[] nums) {heapSort(nums);return nums[nums.length/2];}/*** 堆排序* 大顶堆，升序* @param arr*/public void heapSort(int arr[]){//第一次构建大顶堆，需要单独来，剩下的无所谓//1. 将序列构建成大顶堆，length/2-1是第一个非叶子结点，length/2-2是第二个非叶子结点，依次类推，0是整个序列根结点for(int i = arr.length/2-1;i>=0;i--){adjustHeap(arr,i, arr.length);}//2. 上面构建了一次大顶堆，获取一个最大值，接下来交换，然后构建剩下的大顶堆，让其余最大值有序for (int i = arr.length-1; i > 0; i--) {//堆顶元素与末尾元素交换，此时最大值保存在末尾，length需要--arr[i] = arr[i]^arr[0];arr[0] = arr[i]^arr[0];arr[i] = arr[i]^arr[0];//重新调整结构，构建剩下的大顶堆。使其满足堆定义，继续交换，直到整体有序adjustHeap(arr,0,i);}}/*** 以i下标指定元素作为根结点构建大顶堆，只考虑i节点本身，和所有子孙节点，不考虑其它结点* @param arr 数组* @param i 非叶子结点在数组中索引，以它为根构建大顶堆* @param length 对多少个元素进行调整，逐渐减少，每次都有一个最大值，无需再次构建*/public void adjustHeap(int arr[],int i,int length){int temp = arr[i];//保存当前非叶子结点//以i为根构建大顶堆，i*2+1是当前结点的左子结点，k*2+1是k结点的左子结点下标for(int k = i*2+1;k<length;k=k*2+1){if(k+1<length && arr[k]<arr[k+1]) k++;//如果右节点>左节点，直接考虑右节点if(arr[k]>temp){//k是i结点左右子结点较大的，如果它>i节点，将其值赋值给i结点arr[i] = arr[k];i = k;}else break;//否则不交换值}arr[i] = temp;//此时大顶堆完成，最大值到了最顶部，而i是需要交换的下标，最开始将值保存在temp中，现在赋值过去}
}

刷题一定要坚持，总结套路，不单单要把题做出来，要举一反三，也要参考别人的思路，学习别人解题的优点，找出你觉得可以优化的点。

1. 单链表解题思路：双指针、快慢指针、反转链表、预先指针

1. 双指针：对于单链表而言，可以方便的让我们遍历结点，并做一些额外的事
2. 快慢指针：常用于找链表中点，找循环链表的循环点，一般快指针每次移动两个结点，慢指针每次移动一个结点。
3. 反转链表：通常有些题，将链表反转后会更好做，一般选用三指针迭代法，递归的空间复杂度有点高
4. 预先指针：常用于找结点，比如找倒数第3个结点，那么定义两个指针，第一个指针先移动3个结点，然后两个指针一起遍历，当第一个指针遍历完成，第二个指针指向的结点就是要找的结点

2. 数组解题思路：双指针、三指针，下标标记

1. 双指针：多用于减少时间复杂度，快速遍历数组
2. 三指针：多用于二分查找，分为中间指针，左和右指针
3. 下标标记：常用于在数组范围内找东西，而不想使用额外的空间的情况，比如找数组长度为n，元素取值范围为[1,n]的数组中没有出现的数字，遍历每个元素，然后将对应下标位置的元素变为负数或者超出[1,n]范围的正数，最后没有发生变化的元素，就是缺少的值。
4. 差分数组：对差分数组求前缀和即可得到原数组

1. 用差值，作为下标，节省空间找东西。比如1900年到2000年，就可以定义100大小的数组，每个数组元素下标的查找为1900。
2. 前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 ii个数即为原数组的第 i-1 个元素和第 i个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组

5. 前缀和：假设有一个数组arr[1,2,3,4]。然后创建一个前缀和数组sum，记录从开头到每个元素区间的和。第一个元素是0。第二个元素，保存第一个和sum[1] = sum[0]+arr[0]，第二个元素，保存第二个和sum[2] = sum[1]+arr[1]
6. 位运算，异或。不使用额外空间找东西可用

1. 任何数异或0 都为本身。a^0 = a
2. 自己异或自己 = 0。a^a = 0
3. 满足交换律：a^ba = b^aa = b^(aa) = b^0 = b

3. 栈解题思路：倒着入栈，双栈

1. 倒着入栈：适用于出栈时想让输出是正序的情况。比如字符串’abc’，如果倒着入栈，那么栈中元素是（c,b,a）。栈是先进后出，此时出栈，结果为abc。
2. 双栈：适用于实现队列的先入先出效果。一个栈负责输入，另一个栈负责输出。