ค่าที่ใหญ่ที่สุดจากป้ายกำกับใน Python

สมมติว่าเรามีชุดของรายการ:รายการ i-th มีค่า value[i] และ label labels[i] จากนั้น เราจะนำเซตย่อย S ของรายการเหล่านี้ −

• |ส| <=num_wanted
• สำหรับทุกป้ายกำกับ L จำนวนรายการที่แสดงใน S ที่มีป้ายกำกับ L คือ <=use_limit

เราต้องหาผลรวมที่ใหญ่ที่สุดของเซตย่อย S.

ตัวอย่างเช่น หากอินพุตมีค่าเท่ากับ =[5,4,3,2,1] และป้ายกำกับคือ [1,1,2,2,3], num_wanted =3, use_limit =1 ผลลัพธ์จะเป็น 9 . นี่เป็นเพราะเซ็ตย่อยถูกเลือกในรายการที่หนึ่ง สาม และห้า

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างหนึ่งอาร์เรย์ v
• สำหรับ i ในช่วง 0 ถึงความยาวของค่า
  • แทรก [values[i], labels[i]] ลงใน v
• เรียงลำดับ v อาร์เรย์
• ตอบ :=0 ใช้ :=แผนที่ว่าง และ i :=0
• ในขณะที่ num_wanted และ i <ความยาวของ v
  • ถ้า v[i, 1] ไม่มีอยู่ในแผนที่ใช้งาน
    • ลดลง num_wanted โดย 1
    • ans :=ans + v[i, 0]
    • ใช้[v[i, 1]] :=1
  • ใช้อย่างอื่น[v[i, 1]]
  • ลดลง num_wanted โดย 1
  • ans :=ans + v[i, 0]
  • เพิ่มการใช้งาน[v[i, 1]] 1
• เพิ่ม i ขึ้น 1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution(object):
   def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
      v = []
      for i in range(len(values)):
         v.append([values[i],labels[i]])
      v = sorted(v,key = lambda v:v[0],reverse=True)
      ans = 0
      use = {}
      i = 0
      while num_wanted and i < len(v):
         if v[i][1] not in use:
            num_wanted -=1
            ans+=v[i][0]
            use[v[i][1]] = 1
         elif use[v[i][1]]<use_limit:
            num_wanted -=1
            ans+=v[i][0]
            use[v[i][1]]+=1
         i+=1
      return ans
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1],[1,1,2,2,3],3,1))

อินพุต

[5,4,3,2,1]
[1,1,2,2,3]
3
1

ผลลัพธ์

9