KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5


Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4


Constraints:

n == arr.length 1 <= n <= 10<sup>5</sup>
* 1 <= arr[i] <= 10<sup>5</sup>

题目大意：

求相同元素的下标差的和

解题思路：

暴力法是TLE，由于存在重复计算。用prefix和suffix来优化。
prefix为从某个元素为起点到前继节点下标差之和
suffix为从某个元素为起点到后继节点下标差之和
结果 = prefix[i] + suffix[i]

解题步骤：

  1. 用Map来存储相同元素的下标
  2. 用prefix和suffix来计算每个元素的结果

注意事项：

  1. 一开始用presum表示从起点到其他下标的差之和。这不能用于某个元素的前继元素下标差之和。所以要改成从某个元素为起点到前继节点下标差之和

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getDistances(self, arr: List[int]) -> List[int]:
	val_to_index = collections.defaultdict(list)
	res = [0] * len(arr)
	for i in range(len(arr)):
		val_to_index[arr[i]].append(i)
	for val, indices in val_to_index.items():
		prefix, suffix = [0], [0]
		for i in range(1, len(indices)):
			prefix.append(prefix[-1] + i * abs(indices[i] - indices[i - 1]))
		for i in range(len(indices) - 2, -1, -1):
			suffix.append(suffix[-1] + (len(indices) - i - 1) * abs(indices[i] - indices[i + 1]))
		for i in range(len(indices)):
			res[indices[i]] = prefix[i] + suffix[len(indices) - i - 1]
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode



Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
[“WordDistance”, “shortest”, “shortest”]
[[[“practice”, “makes”, “perfect”, “coding”, “makes”]], [“coding”, “practice”], [“makes”, “coding”]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance([“practice”, “makes”, “perfect”, “coding”, “makes”]);
wordDistance.shortest(“coding”, “practice”); // return 3
wordDistance.shortest(“makes”, “coding”);    // return 1


Constraints:

`1 <= wordsDict.length <= 3 104*1 <= wordsDict[i].length <= 10*wordsDict[i]consists of lowercase English letters. *word1andword2are inwordsDict. *word1 != word2* At most5000calls will be made toshortest`.

题目大意：

设计数据结构返回单词列表中两单词下标最短距离。单词列表含重复单词

解题思路：

记录word到下标列表。可以用logn搜索另一个列表，总时间复杂度为O(nlogn)。不如用mergesort的merge来计算，复杂度为O(n)

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class WordDistance(TestCases):

    def __init__(self, wordsDict: List[str]):
        self.word_to_indices = collections.defaultdict(list)
        for i in range(len(wordsDict)):
            self.word_to_indices[wordsDict[i]].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_to_indices[word1]
        indices2 = self.word_to_indices[word2]
        i, j, res = 0, 0, float('inf')
        while i < len(indices1) and j < len(indices2):
            res = min(res, abs(indices1[i] - indices2[j]))
            if indices1[i] <= indices2[j]:
                i += 1
            else:
                j += 1
        return res

算法分析：

shortest时间复杂度为O(L)，空间复杂度O(1)。L为两单词下标列表的最短长度

Posted on Edited on Disqus:

LeetCode



Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure. int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3


Constraints: 0 <= capacity <= 10<sup>4</sup>
0 <= key <= 10<sup>5</sup> 0 <= value <= 10<sup>9</sup>
At most `2 105calls will be made togetandput`.

双Map+分区LL解题思路(推荐)：

类似于LRU，但本质上区别较大。一开始思路可参考算法II，它的缺点是move_up需要从该层的某个位置删除加入到上一个freq较大的下一层的末尾。为了避免此问题，考虑不用单一链表，而是对应不同freq的多个链表。所以引入freq_map来记录每个LL的起点。由于每个LL都是从旧到新（跟LRU一样），新的插入到末尾，删除的从头删除，所以需要是循环链表，最终是一个循环双向LL。ListNode的next和prev都指向自己

move_up解决了，另一个难点是get_lfu_node，这里引入min_freq来记录当前最小的freq。它的更新由三方面引起:新节点min_freq=1，get的move_up和旧节点move_up。后两者是一样的，都是move_up后查看min_freq所以的LL是否为空。

总结一下与LRU的区别：

  • set也是三种情况但要更新min_freq
  • ListNode多了freq，next prev指向自己形成循环LL，key，val含默认值
  • Cache中多了freq map和min_freq
  • 链表操作为move_up和get_lru_node，这点和算法II一样
  • 节点操作为remove_node, add_to_tail和LRU一样。add_to_tail是分层LL末尾不是总链表末尾
题目 LL Map 其他数据结构
LRU 按时间顺序，头删尾入 值->LL节点 N/A
First Unique 按时间顺序，任意删尾入 值->LL节点 Set存两次以上
LFU 多个时间顺序的LL 值->LL节点 第二个Map存freq-> LL的首节点以及min_freq

注意事项：

  1. 用了一小时debug min_freq的更新，move_up发生时候，检查min_freq所在的LL，若为空，增加1，而不是检查node_freq所在的LL。新节点令min_freq变成1
  2. 思路上：LRU是Map to Node in 全局双向LL，而LRU是Map to Node in 分区双向循环LL。存在多条LL，每个LL的起点终点存在freq map中。min_freq记录要删除的LFU节点对应的频率。
  3. 思路上：再LRU基础上增加freq域默认为1，key, val默认为0，prev和next指向自己，形成双向循环LL
  4. capacity可能为0，LRU那天capacity大于0
  5. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.key_to_node = collections.defaultdict(ListNode)
        self.freq_to_head = collections.defaultdict(ListNode)
        self.min_freq = 1
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node_freq = node.freq
            self.move_up(node)
            # if self.freq_to_head[node_freq].next == self.freq_to_head[node_freq]:
              #  self.min_freq = node.freq
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self.move_up(node)
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
        elif self.capacity > 0:
            if len(self.key_to_node) == self.capacity:
                lru_node = self.get_lru_node()
                self.key_to_node.pop(lru_node.key)
                self.remove_node(lru_node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node
            self.min_freq = 1

    def move_up(self, node):
        self.remove_node(node)
        node.freq += 1
        self.add_to_tail(node)

    def get_lru_node(self):
        head = self.freq_to_head[self.min_freq]
        return head.next

    def add_to_tail(self, node):
        head = self.freq_to_head[node.freq]
        predecessor, successor = head.prev, head
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None

class ListNode:

    def __init__(self, key=0, val=0, freq=1):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = self # self-pointed
        self.next = self

算法分析：

Insert时间复杂度为O(1)，空间复杂度O(n)

类LRU算法II解题思路(不推荐)：

似乎Leetcode改变了要求，之前此法是可以通过的，但现在put要求O(1)了，所以TLE了。

注意事项：

  1. 再LRU基础上增加freq域默认为1，新节点插入doubly LL末尾，LL以freq从大到小，同一个频率从最旧到最新(LRU)。所以若满容量要删除节点从freq=1中往前找到该层的首节点
  2. capacity可能为0，LRU那天capacity大于0
  3. move_up是往前搜索, it = it.prev而不是用next。比较条件为it.freq < node.freq，加入到同一频率的末尾
  4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = collections.defaultdict(ListNode)
        # newly inserted to tail
        self.head, self.tail = ListNode(0, 0), ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            self.move_up(self.key_to_node[key])
            return self.key_to_node[key].val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_up(self.key_to_node[key])
        elif self.capacity > 0: # remember
            if len(self.key_to_node) == self.capacity:
                node = self.get_lfu_node()
                self.key_to_node.pop(node.key)
                self.remove(node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node

    def get_lfu_node(self):
        it = self.tail.prev
        min_freq = it.freq
        while it != self.head and it.freq == min_freq:
            it = it.prev # remember prev not next
        return it.next

    def move_up(self, node):
        node.freq += 1
        it = node.prev
        self.remove(node)
        while it != self.head and it.freq < node.freq: # remember <=
            it = it.prev # remember prev not next
        predecessor, successor = it, it.next
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor # remember

    def remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, key, val, freq=1, prev=None, next=None):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = prev
        self.next = next

注意事项：

  1. 在LRU基础上，ListNode引入freq域， 当频率增加时候，找到新的频率对应的末节点插入。其它基本不变。插入最差是O(n). 要提高的话，需要加入map和minFreq来迅速定位下一个插入位置。第一个Map不变，但LL不再是一串，而是按频率大小的多串。

Java代码：

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
Map<Integer, ListNode> map;
ListNode head; // from most frequent to less
ListNode tail;
int capacity;
public L460LFUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1, Integer.MAX_VALUE);
	tail = new ListNode(-1, -1, Integer.MIN_VALUE);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	moveUp(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(capacity == 0)
		return;
	
	if(map.containsKey(key)) {
		moveUp(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(tail.prev.key);
			deleteNode(tail.prev);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNode(newNode, tail);
		map.put(key, newNode);
		moveUp(key);
	}
}

void moveUp(int key) {
	ListNode curNode = map.get(key);
	curNode.addOne();
	ListNode iterNode = curNode;
	while(iterNode.freq <= curNode.freq)
		iterNode = iterNode.prev;
	if(iterNode != curNode) {
		deleteNode(curNode);
		addNode(curNode, iterNode.next);
	}
}

void addNode(ListNode curNode, ListNode nextNode) {
	ListNode prevNode = nextNode.prev;
	prevNode.next = curNode;
	curNode.prev = prevNode;
	curNode.next = nextNode;
	nextNode.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public int freq = 1;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
	
	public ListNode(int key, int val, int freq) {
		this.key = key;
		this.val = val;
		this.freq = freq;
	}
	
	public void addOne() {
		freq++;
	}
}

算法分析：

Insert时间复杂度为O(n)，空间复杂度O(k)

Posted on Edited on Disqus:

LeetCode



Let’s play the minesweeper game (Wikipedia), online game)!

You are given an m x n char matrix board representing the game board where:

'M' represents an unrevealed mine, 'E' represents an unrevealed empty square,
'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals), digit ('1' to '8') represents how many mines are adjacent to this revealed square, and
'X' represents a revealed mine.

You are also given an integer array click where click = [click<sub>r</sub>, click<sub>c</sub>] represents the next click position among all the unrevealed squares ('M' or 'E').

Return the board after revealing this position according to the following rules:

1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
2. If an empty square 'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square 'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

Example 1:



Input: board = [[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”M”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”]], click = [3,0]
Output: [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”M”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]]


Example 2:



Input: board = [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”M”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]], click = [1,2]
Output: [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”X”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]]


Constraints: m == board.length
n == board[i].length 1 <= m, n <= 50
board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'. click.length == 2
0 <= click<sub>r</sub> < m 0 <= click<sub>c</sub> < n
* board[click<sub>r</sub>][click<sub>c</sub>] is either 'M' or 'E'.

题目大意：

给定扫雷版上的某一个状态，计算扫雷版上的下一个状态

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 三种情况： 1. 踩雷，只需更改此格。 2. 踩到数字格也就是雷相邻的格，计算此格的临近雷数，更改此格。 3. 从此格开始BFS访问全版，节点出列后如果是数字格不加入到queue中，否则继续BFS访问，更改此格。
  2. x, y = node[0] + _dx, node[1] + _dy用node[0], node[1]不要用i, j

Python代码：

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
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

	if board[click[0]][click[1]] == 'M':
		board[click[0]][click[1]] = 'X'
		return board
	else:
		mine_num = self.get_neighboring_mine_num(board, click[0], click[1])
		if mine_num > 0:
			board[click[0]][click[1]] = str(mine_num)
			return board
		else:
			return self.bfs(board, click[0], click[1])

def bfs(self, board, i, j):
	queue = collections.deque([(i, j)])
	visited = set([(i, j)])
	while queue:
		node = queue.popleft()
		mine_num = self.get_neighboring_mine_num(board, node[0], node[1])
		if mine_num > 0:
			board[node[0]][node[1]] = str(mine_num)
			continue
		else:
			board[node[0]][node[1]] = 'B'
		for _dx, _dy in OFFSETS:
			x, y = node[0] + _dx, node[1] + _dy # remember not to use i, j
			if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or (x, y) in visited:
				continue
			queue.append((x, y))
			visited.add((x, y))
	return board

def get_neighboring_mine_num(self, board, i, j):
	num = 0
	for _dx, _dy in OFFSETS:
		x, y = i + _dx, j + _dy
		if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] == 'M':
			num += 1
	return num

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Posted on Edited on Disqus:

LeetCode 540 Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1: 

**Input:** [1,1,2,3,3,4,4,8,8]
**Output:** 2

Example 2: 

**Input:** [3,3,7,7,10,11,11]
**Output:** 10

Note: Your solution should run in O(log n) time and O(1) space.

题目大意：

一个有序数组中，每个数字都出现了两次，只有一个数字出现了一次，求出现一次的数字。

解题思路：

这是A公司Problem solving的题目。类似于L136。此题数组有序且要求O(logn)时间，所以考虑用二分法。由于没有输入tgt，有点似
算法文档中用二分法求峰值，就是比较相邻两个数做二分法。考虑一个结论，若数组为偶数个数，就一定不存在只出现一次的元素。
所以必须考虑奇偶位，若下标mid为偶数，其后一位与其相等，就一定在右半边搜索left=mid+2(不会是mid和mid+1)，如第二个
例子，因为mid左边个数为偶数，利用结论可知不会在左边。同理与后一位不等，搜左边right=mid(可能为mid)。注意边界。
若mid为奇数，mid前面有奇数个，mid包括自己的后面有偶数个，所以mid和mid+1上的数相等，就应在左半搜，所以与偶数位的
情况正好相反，但是边界不同，产生了4个if语句。
法二：改进一下，若mid为奇数位，就mid–归结为偶数位的情况，这样if变成两个。

注意事项：

  1. 类似于Leetcode 033，四种情况，前两种中的第二种全包第一种。
  2. for循环后，答案一定在start和end其中一个。end前面有偶数个与start不同就肯定在start上。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def singleNonDuplicate(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) //2
		if mid % 2 == 1 and mid >= 1 and nums[mid - 1] == nums[mid]:
			start = mid
		elif mid % 2 == 1:
			end = mid
		elif mid % 2 == 0 and mid >= 1 and nums[mid - 1] != nums[mid]:
			start = mid
		else:
			end = mid
	if end % 2 == 1 and nums[start] != nums[end]:
		return nums[start] # remember
	else:
		return nums[end]

注意事项：

  1. 边界也就是mid的赋值，写出例子来理解。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int singleNonDuplicate(int[] nums) {
	int N = nums.length;
	int left = 0, right = N - 1;
	while (left < right) {
		int mid = (right - left) / 2 + left;
		boolean isEven = true;
		if (mid % 2 == 1) isEven = false;
		if ((isEven && nums[mid] != nums[mid + 1]) )
			right = mid;
		else if (isEven && nums[mid] == nums[mid + 1])
			left = mid + 2;
		else if (!isEven && nums[mid] == nums[mid + 1])
			right = mid-1;
		else
			left = mid + 1;
	}
	return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public int singleNonDuplicate2(int[] nums) {
	  int N = nums.length;
	  int left = 0, right = N - 1;
	  while (left < right) {
		  int mid = (right - left) / 2 + left;
		  if (mid % 2 == 1) mid--;
		  if (nums[mid] != nums[mid + 1])
			  right = mid;
		  else
			  left = mid + 2;
	  }
	  return nums[left];
}

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。

Follow-up:

首先问L316 Given a non-empty array of integers, every element appears twice except for one. Find that single one.
XOR解法，不用实现。
Follow up问题是L260 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
分三步。若只有一个数出现1次，只要把所有数异或^即可(相同数异或=0)。如果有两个此数，异或结果是这两数不同的位。只要选为1且最低位(或任意为1的位)lowBit=a-(a&(a-1))。再扫所有数，根据它们在lowBit上=0和=1分组异或num1, num2，最后分组异或后它们为所求

Free mock interview