难度: Medium
Submission
运行时间: 48 ms
内存: 17.4 MB
# """ # This is the ArrayReader's API interface. # You should not implement it, or speculate about its implementation # """ #class ArrayReader(object): # # Compares 4 different elements in the array # # return 4 if the values of the 4 elements are the same (0 or 1). # # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa. # # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1. # def query(self, a: int, b: int, c: int, d: int) -> int: # # # Returns the length of the array # def length(self) -> int: # class Solution: def guessMajority(self, reader: 'ArrayReader') -> int: n = reader.length() qs = [reader.query(1, 2, 3, 4), reader.query(0, 2, 3, 4), reader.query(0, 1, 3, 4), reader.query(0, 1, 2, 4), reader.query(0, 1, 2, 3)] e0 = [] #记录1234中与0相同的索引 e1 = [] #记录1234中与0不同的索引 for i in range(1, 5): if qs[i] == qs[0]: e0.append(i) else: e1.append(i) count0 = 0 # 与索引0相同的数量 count1 = 0 # 与索引0不同的数量 other_idx = -1 if len(e0) == 4: # 1234中共有5种情况,分开写易于理解 count0 = 5 count1 = 0 for i in range(5, n): if reader.query(0, 1, 2, i)!=4: other_idx = i count1 += 1 else: count0 += 1 elif len(e0) == 3: count0 = 4 count1 = 1 other_idx = e1[0] for i in range(5, n): if reader.query(0, e0[0], e0[1], i)!=4: count1 += 1 else: count0 += 1 elif len(e0) == 2: count0 = 3 count1 = 2 other_idx = e1[0] for i in range(5, n): if reader.query(0, e0[0], e0[1], i)!=4: count1 += 1 else: count0 += 1 elif len(e0) == 1: count0 = 2 count1 = 3 other_idx = e1[0] for i in range(5, n): if reader.query(e1[0], e1[1], e1[2], i)!=4: count0 += 1 else: count1 += 1 elif len(e0) == 0: count0 = 1 count1 = 4 other_idx = e1[0] for i in range(5, n): if reader.query(e1[0], e1[1], e1[2], i)!=4: count0 += 1 else: count1 += 1 if count0 == count1: return -1 elif count0 > count1: return 0 else: return other_idx
Explain
这个题解通过使用 ArrayReader 的 query 和 length 方法来推断出数组中元素的多数元素。首先,使用 query 方法对前5个元素进行两两比较,得到五个查询结果。通过比较这些结果,确定哪些索引的元素与第一个元素相同或不同。然后,根据这些信息,我们可以推断出数组中0索引元素和其他元素(与0索引不同的元素)的出现频率。接着,对数组中剩余的元素进行查询,以确定它们与已知元素的相似性,从而更新两种元素的计数。最后,比较两种元素的数量,返回出现次数较多的元素的索引。如果两者出现次数相同,则返回-1。
时间复杂度: O(n)
空间复杂度: O(1)
# This is the ArrayReader's API interface. # You should not implement it, or speculate about its implementation # class ArrayReader(object): # \t # Compares 4 different elements in the array # \t # return 4 if the values of the 4 elements are the same (0 or 1). # \t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa. # \t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1. # def query(self, a: int, b: int, c: int, d: int) -> int: # # \t # Returns the length of the array # def length(self) -> int: # class Solution: def guessMajority(self, reader: 'ArrayReader') -> int: n = reader.length() qs = [reader.query(1, 2, 3, 4), reader.query(0, 2, 3, 4), reader.query(0, 1, 3, 4), reader.query(0, 1, 2, 4), reader.query(0, 1, 2, 3)] e0 = [] # Records indices that have the same value as index 0 e1 = [] # Records indices that have different value from index 0 for i in range(1, 5): if qs[i] == qs[0]: e0.append(i) else: e1.append(i) count0 = 0 # Count of elements same as index 0 count1 = 0 # Count of elements different from index 0 other_idx = -1 if len(e0) == 4: # All elements are the same as index 0 count0 = 5 count1 = 0 for i in range(5, n): if reader.query(0, 1,2, i) != 4: other_idx = i count1 += 1 else: count0 += 1 elif len(e0) == 3: # Three elements are the same as index 0 count0 = 4 count1 = 1 other_idx = e1[0] for i in range(5, n): if reader.query(0, e0[0], e0[1], i) != 4: count1 += 1 else: count0 += 1 elif len(e0) == 2: # Two elements are the same as index 0 count0 = 3 count1 = 2 other_idx = e1[0] for i in range(5, n): if reader.query(0, e0[0], e0[1], i) != 4: count1 += 1 else: count0 += 1 elif len(e0) == 1: # One element is the same as index 0, three are different count0 = 2 count1 = 3 other_idx = e1[0] for i in range(5, n): if reader.query(e1[0], e1[1], e1[2], i) != 4: count0 += 1 else: count1 += 1 elif len(e0) == 0: # No elements are the same as index 0 count0 = 1 count1 = 4 other_idx = e1[0] for i in range(5, n): if reader.query(e1[0], e1[1], e1[2], i) != 4: count0 += 1 else: count1 += 1 if count0 == count1: return -1 elif count0 > count1: return 0 else: return other_idx
Explore
ArrayReader的query方法通过比较特定的四个元素来返回一个整数,这个整数描述了这四个元素之间的相似性或差异性。具体映射为:如果返回4,表示这四个元素值相同;返回2,表示其中三个元素值相同,另一个不同;返回0,表示两个元素值相同,另两个也相同但与前两个不同。这样的返回值使我们能够推断哪些元素可能具有相同的值,从而对数组中的元素多数性质进行推断。
当初次查询的结果显示所有比较的元素与索引0的元素相同(即query返回值为4时),这意味着这五个元素都具有相同的值。因此,初始时将count0设置为5,是因为已经有确凿的证据表明这五个元素是相同的。这并不意味着数组中其他未查询的元素也与索引0相同,对于数组中剩余的元素,还需要进行后续的查询来确定它们是否与索引0相同。
在len(e0)等于3的情况下,意味着有三个元素与索引0的元素具有相同的值,而只有一个元素(即e1[0])与索引0的元素不同。因此,other_idx被设置为e1[0],代表这个与众不同的元素的索引,这是因为在这种情况下我们已经确切地知道哪个元素与索引0不同。后续的查询会围绕这个已知不同的元素和已知相同的元素,来进一步确认数组中其他元素的值。