LeetCode169（求众数）

发表于 | 分类于 ，

题目：

　　给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于n/2的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

思路：

　　此题解法众多。
1.数据出现次数问题想到可以使用哈希表
2.可先对数组排序，然后去n/2位置处的数据即为众数
3.利用

代码：

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
			return null;
		}
        ListNode node1 = headA;
        ListNode node2 = headB;
        int countA = 0;
        int countB = 0;
        while(node1 != null) {
        	countA++;
        	node1 = node1.next;
        }
        while(node2 != null) {
        	countB++;
        	node2 = node2.next;
        }
        ListNode node3 = headA;
        ListNode node4 = headB;
        if (countA > countB) {
			for(int i = 0;i < countA - countB;i++) {
				node3 = node3.next;
			}
		}else {
			for(int i = 0;i < countB - countA;i++) {
				node4 = node4.next;
			}
		}
        while(node3 != null && node4 != null) {
        	if (node3 == node4) {
				return node3;
			}
        	node3 = node3.next;
        	node4 = node4.next;
        }
        return null;
    }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。