java数据结构与算法刷题-----LeetCode169：多数元素_数据结构与算法java 刷题

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 2
        count        1 2
        第三次，重复步骤，count!=0,继续用candidate比较，此时candidate与数组元素1不一致，count--
                    [2,2,1,1,1,2,2]
        candidate    2 2 2
        count        1 2 1
        第四次，又不一样，--
                    [2,2,1,1,1,2,2]
        candidate    2 2 2 2
        count        1 2 1 0
        第五次，count == 0，那么candidate就变为当前元素值1.然后再比较
                    [2,2,1,1,1,2,2]
        candidate    2 2 2 2 1
        count        1 2 1 0 1
        第六次，count！=0，但是candidate不一致，count--
                    [2,2,1,1,1,2,2]
        candidate    2 2 2 2 1 1
        count        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 2
        count        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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

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

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. 双栈：适用于实现队列的先入先出效果。一个栈负责输入，另一个栈负责输出。