Python의 레이블에서 가장 큰 값

<시간/>

항목 집합이 있다고 가정합니다. i 번째 항목에는 값 값[i]과 레이블 레이블[i]이 있습니다. 그런 다음 이러한 항목의 하위 집합 S를 다음과 같이 취합니다. -

|S| <=num_wanted
모든 레이블 L에 대해 레이블 L이 있는 S에 있는 항목 수는 <=use_limit입니다.

부분집합 S의 가능한 가장 큰 합을 찾아야 합니다.

예를 들어 입력이 values =[5,4,3,2,1]이고 레이블이 [1,1,2,2,3], num_wanted =3, use_limit =1인 경우 출력은 9가 됩니다. . 첫 번째, 세 번째, 다섯 번째 항목에서 하위 집합을 선택했기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 배열 v
0에서 값의 길이까지 범위에 있는 i의 경우
- v에 [값[i], 레이블[i]] 삽입
v 배열 정렬
ans :=0, :=빈 맵 사용, i :=0
num_wanted와 i 의 길이
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