Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm ra chỉ mục của phần tử thường xuyên nhất trong một mảng ẩn bằng Python

Giả sử, chúng ta được cung cấp một lớp gọi là 'TestArray' chứa một mảng riêng chỉ có thể chứa các giá trị 0 hoặc 1; và hai hàm thành viên công khai length () và query (). Hàm length () trả về độ dài của mảng và truy vấn hàm () trả về ba giá trị khác nhau so sánh các giá trị khác nhau trong mảng. Hàm nhận bốn giá trị p, q, r, s làm đầu vào và hoạt động như thế này -

  • nếu tất cả bốn giá trị trong các chỉ mục nhất định của mảng là 0 hoặc 1, nó sẽ trả về 4.

  • khác nếu bất kỳ ba giá trị nào trong các chỉ mục đã cho của mảng giống nhau và giá trị thứ tư khác nhau, thì nó sẽ trả về 2.

  • khác nếu mảng chứa hai giá trị 0 và hai giá trị 1 trong các chỉ mục nhất định của mảng, thì nó trả về 0.

Chúng ta phải tìm ra chỉ số của phần tử xuất hiện nhiều nhất trong mảng mà không cần truy cập vào chính mảng đó và chỉ sử dụng các hàm thành viên của lớp. Nếu có cùng số 0 và 1 trong mảng, nó trả về giá trị -1.

Vì vậy, nếu đầu vào giống như mảng =[0, 1, 1, 0, 1, 1, 1, 0]., Thì đầu ra sẽ là 2 Trong chỉ số 2 của mảng, giá trị là 1 là giá trị thường gặp nhất giá trị trong mảng. Tương tự, các câu trả lời 1, 4, 5, 6 cũng đúng vì các chỉ mục cũng chứa giá trị 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • n:=length ()

  • groupA:=1

  • nhómB:=0

  • aIdx:=null

  • bIdx:=null

  • đầu tiên:=:=query (0, 1, 2, 3)

  • thứ hai:=truy vấn (0, 1, 2, 4)

  • đối với tôi trong phạm vi 4 đến n, hãy làm

    • nếu truy vấn (0, 1, 2, i) giống với truy vấn đầu tiên, thì

      • groupA:=groupA + 1

      • aIdx:=i

    • nếu không,

      • groupB:=groupB + 1

      • bIdx:=i

  • đối với tôi trong phạm vi từ 0 đến 2, hãy thực hiện

    • nxt:=danh sách mới

    • đối với v trong phạm vi từ 1 đến 4, thực hiện

      • nếu v không giống với tôi, thì

        • thêm v vào cuối nxt

    • nếu truy vấn (các giá trị của nxt) giống như truy vấn thứ hai, thì

      • groupA:=groupA + 1

      • aIdx:=i

    • nếu không,

      • groupB:=groupB + 1

      • bIdx:=i

  • nếu groupA> groupB thì

    • trả về aIdx

  • ngược lại, nếu groupB> groupA, thì

    • trả về aIdx

  • nếu không,

    • trả về -1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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))

Đầu vào 

[0, 1, 1, 0, 1, 1, 1, 0]

Đầu ra 

2