难度: 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不同。后续的查询会围绕这个已知不同的元素和已知相同的元素，来进一步确认数组中其他元素的值。