資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
first := query(0, 1, 2, 3)
second := query(0, 1, 2, 4)
for i in range(4, n):
if query(0, 1, 2, i) == first:
groupA := groupA + 1
aIdx := i
else:
groupB := groupB + 1
bIdx := i
for i in range(0, 3):
nxt = []
for v in range(1, 4):
if v != i:
nxt.append(v)
if query(nxt) == second:
groupA := groupA + 1
aIdx := i
else:
groupB := groupB + 1
bIdx := i
if groupA > groupB:
return aIdx
else if groupB > groupA:
return aIdx
else:
return -1
示例 (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
194 次瀏覽
