[리트코드 leetcode]

by

색인

    쉬운 목차

    개요

    표시된 지수의 최대 수 찾기 – LeetCode


    '추천 관련글,

    숫자 배열이 주어집니다.

    이 배열에서 위의 식을 만족하는 인덱스 쌍을 표시합니다.

    태그가 지정되지 않은 쌍만 페어링할 수 있습니다.

    이러한 쌍의 최대 수를 반환합니다.

    설명

    처음에 나는 그것이 max 요소를 반환하는 것에 관한 것이라고 생각하면서 약간 길을 잃었습니다.


    결국 그것은 쌍을 찾는 문제일 뿐이고 해당 쌍의 최대값은 nums 배열의 절반입니다.


    이를 염두에 두고 문제를 해결해 봅시다.

    배열에 관계없이 정답의 최대값은 배열 길이의 절반입니다.


    위의 정렬된 배열에서 i와 j 쌍(i는 j보다 작음)을 찾는 것을 고려하면 c가 i가 되는 경우가 있습니까? i와 마찬가지로 c도 쌍에 속할 가능성이 있습니다.

    1,2,3,4,6 배열이 주어지면 3,6 쌍이 생성됩니다.

    그러나 배열에서 정답, 즉 쌍의 수는 c가 반드시 쌍이 되지 않더라도 2입니다.

    내 말은 배열을 가져와 정렬하면 중앙값과 큰 값은 쌍에 속하지만 작은 값은 쌍에 속하지 않는다는 것입니다.

    이를 고려하여 두 개의 포인터 알고리즘을 사용할 수 있습니다.

    암호

    class Solution:
    def maxNumOfMarkedIndices(self, nums: List(int)) -> int:
        n = len(nums)
        inlst = sorted(nums)
        ans = 0
        i, j = 0, n // 2
        while i < n//2 and j < n:
            if inlst(i) * 2 <= inlst(j):
                ans += 2
                i += 1
            j += 1
        return ans