분할 가능한 쌍 계산


난이도 중급
자주 묻는 질문 마힌 드라 콤비 바 신탁
배열 동적 프로그래밍 해시 해싱

Divisible Pairs는 면접관이 가장 좋아하는 문제 중 하나입니다. 이 문제는 배열 및 해시 맵과 같은 주제에 대한 지식과 함께 인터뷰 대상자의 문제 기술을 테스트하기에 충분합니다.

문제 설명:

우리는 뚜렷한 양의 정수.

무엇을 찾을까요?

하위 집합의 각 요소가 하나의 규칙을 따르는 쌍의 수 :

  1. 요소 (i) % 요소 (j) = 0
  2. 요소 (j) % 요소 (i) = 0

즉, 각 요소가 다른 요소를 나눕니다.

접근 방식 -1

브 루트 포스

나눌 수있는 쌍을 계산하기위한 Java 코드

class Solution 
{
    public int largestDivisibleSubset(int[] nums) 
    {
    int count=0;
    for(int i=0;i<nums.length;i++)
    {
        for(int j=i+1;j<nums.length;j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
}

나눌 수있는 쌍을 계산하기위한 C ++ 코드

class Solution
{
public:
    int largestDivisibleSubset(vector<int>& nums) 
    {
    vector<int>data;
    int count=0;
    for(int i=0;i<nums.size();i++)
    {
        for(int j=i+1;j<nums.size();j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
};
[1,2,3,9]
3

시간 복잡도 = O (n ^ 2)

이유는 무엇입니까?

  • 위 코드에서 실행되는 두 개의 루프
  • 먼저 첫 번째 요소를 캡처하는 배열에서 실행되는 루프 -O (n)
  • 둘째, 두 번째 요소를 캡처하는 첫 번째 루프 내부에서 실행되는 루프 -O (n)
  • 결론적으로 우리는 O (n ^ 2)의 시간 복잡도로 끝납니다.

공간 복잡성 = O (1)

작은 조정

모든 하위 집합 중에서 나눌 수있는 가장 큰 하위 집합을 반환하라는 요청을 받으면 어떻게됩니까?

당신은 몇 개의 연속 쌍을 세고 인터뷰를 피하는 것을 고려할 수 있습니다!. 내가 가장 쉽게 할 수 있고 해결책을 이해할 수 있도록 도와 드리겠습니다. 먼저 접근 방식을 사용하는 쉬운 XNUMX 단계로 나눌 것입니다. DP.

  • 먼저 배열 정렬
  • 배열을 정렬하면 배열의 분할이 그 앞에 표시됩니다.
  • 둘째, 배열 개수 생성
  • 카운트 배열은 만난 숫자의 제수 수를 저장합니다.
  • 가장 큰 하위 집합이 필요하므로 카운트 가장 큰 것을 찾으십시오.
  • 세 번째로 요소에서 제수를 추가하여 하위 집합을 완성합니다.

하나의 그림이 천 단어를 말하는 것처럼 그림으로 같은 것을 설명하겠습니다.

나눌 수있는 쌍 시놉시스
나눌 수있는 쌍 시놉시스

자바 코드

class Solution
{
    public List<Integer> largestDivisibleSubset(int[] nums) 
    {
        Arrays.sort(nums);
        List<Integer>lisa=new ArrayList<Integer>();
        if(nums.length==0)
            return lisa;
        int count[]=new int[nums.length];
        int max=Integer.MIN_VALUE;
        Arrays.fill(count,1);
        for(int i=1;i<nums.length;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=Math.max(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.length;i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            System.out.println(nums[i]+" "+temp+" "+count[i]);
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.add(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
}

C ++ 코드

class Solution
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end()); 
        vector<int>lisa;
        if(nums.size()==0)
            return lisa;
        vector<int>count(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=maxs(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.size();i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.push_back(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
};

나눌 수있는 쌍에 대한 복잡성 분석

발생한 시간 복잡도 = O (n ^ 2)

필요한 공간 = O (n)

우리가 상기 시간 및 공간 복잡성에 도달 한 방법에 대한 분석

공간 복잡성

  • 두 개의 추가 공간을 만듭니다.
  • First- 결과를 저장할 배열
  • 배열의 최대 길이-입력 배열의 길이 = O (n)
  • Second-An 배열은 서브 세트의 길이를 저장합니다.
  • 배열의 길이-입력 배열의 길이 = O (n)

시간 복잡성

  • 첫째, 배열 정렬에 걸린 시간 = O (n log n)
  • 둘째, 부분 집합을 찾는 데 걸리는 시간 = O (n ^ 2)
  • 어떻게?
  • 우리는 두 개의 루프를 실행합니다.
  • 외부 루프는 배열의 각 요소를 고려합니다.
  • 내부 루프는 제수 수를 추가하는 데 도움이됩니다.
  • 마지막으로,이 모든 것이 O (n ^ 2) + O (nlogn)의 시간 복잡도로 이어집니다.
  • N ^ 2가 클수록 전체 문제의 시간 복잡도 O (n ^ 2)