在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
对于范围内的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))