在Python中查找隐式数组中最频繁的元素的索引
假设我们有一个名为“TestArray”的类,它包含一个私有数组,该数组只能包含值0或1;以及两个公共成员函数length()和query()。函数length()返回数组的长度,函数query()返回比较数组中各个值的三个不同的值。该函数输入四个值p、q、r、s,工作如下:
- 如果数组中给定索引的所有四个值都是0或1,则返回4。
-
否则,如果给定索引的任何三个值相同,第四个值不同,则返回2。
-
否则,如果数组在给定索引的数组中包含两个值0和两个值1,则返回0。
我们必须找出数组中最频繁的元素的索引,而不访问数组本身,仅使用类的成员函数。如果数组中有相同数量的0和1,则返回值为-1。
因此,如果输入为array = [0, 1, 1, 0, 1, 1, 1, 0],则输出将为2。在数组的索引2处,值为1,这是数组中最频繁的值。类似地,答案1、4、5、6也是正确的,因为索引也包含值1。
要解决这个问题,我们将按以下步骤进行 –
- n:= length()
-
groupA:=1
-
groupB:= 0
-
aIdx:= null
-
bIdx:= null
-
第一次:=查询(0,1,2,3)
-
第二:=查询(0,1,2,4)
-
对于范围内的i为4到n,执行
- 如果查询(0,1,2,i)与first相同,则
- groupA:= groupA+1
-
aIdx:= i
-
否则,
- groupB:= groupB+1
-
bIdx:= i
- 如果查询(0,1,2,i)与first相同,则
-
对于范围内的i为0到2,执行
- nxt:=新列表
-
对于v在1到4范围内,执行
- 如果v与i不同,则
-
将v添加到nxt的末尾
-
如果查询(nxt的值)与second相同,则
- groupA:= groupA + 1
-
aIdx:= i
-
否则,
- groupB:= groupB+1
-
bIdx:= i
-
如果groupA> groupB,那么
- return aIdx
- 否则,如果groupB> groupA,那么
- return bIdx
- 否则,
- return -1
更多Python相关文章,请阅读:Python 教程
示例(Python)
让我们看下面的实现,以获得更好的理解 –
class TestArray:
def __init__(self, array) -> None:
self.__arr = array
def length(self):
return len(self.__arr)
def query(self, p, q, r, s):
val = self.__arr[p] + self.__arr[q] + self.__arr[r] + self.__arr[s]
if val == 4 or val == 0:
return 4
elif val == 1 or val == 3:
return 2
elif val == 2:
return 0
def solve(reader):
n,groupA,groupB,aIdx,bIdx=reader.length(),1,0,None,None
first,second=reader.query(0,1,2,3),reader.query(0,1,2,4)
for i in range(4,n):
if reader.query(0,1,2,i)==first:
groupA,aIdx=groupA+1,i
else:
groupB,bIdx=groupB+1,i
for i in range(3):
nxt=[v for v in [0,1,2,3,4] if v!=i]
if reader.query(*nxt)==second:
groupA,aIdx=groupA+1,i
else:
groupB,bIdx=groupB+1,i
return aIdx if groupA>groupB else bIdx if groupB>groupA else -1
arr_ob = TestArray([0, 1, 1, 0, 1, 1, 1, 0])
print(solve(arr_ob))
输入
[0, 1, 1, 0, 1, 1, 1, 0]
输出
2