검지 의 혜택 - 49: 미 운 수

제목 설명
질 인자 2, 3, 5 만 포 함 된 수 를 축 수 (Ugly Number) 라 고 한다.예 를 들 어 6, 8 은 모두 못 생 긴 숫자 이지 만 14 는 그렇지 않다. 왜냐하면 그것 은 질 인자 7 을 포함 하기 때문이다.습관 적 으로 우 리 는 1 을 첫 번 째 못 생 긴 숫자 로 여 긴 다.어 릴 때 부터 큰 순서 로 N 번 째 축 수 를 구하 세 요.
질 인자 라 니 요?
255 이 수 를 예 로 들 어 질 인 자 는 바로 질 수의 인자 이 고 질 인수 나 질 약수 라 고도 부른다.255 의 인 자 는 1, 3, 5, 15, 17, 51, 85, 255 이다.그 중에서 질 수 는 1, 3, 5, 17 이기 때문에 255 의 질 인 자 는 1, 3, 5, 17 이다.그래서 최대 질 인 자 는 17 이다.55 는 255 의 인자 도 아니 고 질 수도 아니 며 당연히 255 의 최대 질 인자 도 아니다.
문제 풀이 의 사고 방향.
하나의 숫자 가 추악 한 숫자 인지 아 닌 지 를 판단 하 는 가장 간단 한 방법 은 이 숫자 를 끊임없이 2, 3, 5 로 나 누 는 것 이다.N 번 째 축 수 를 요구 하 는데 1 부터 각 수가 축 수 인지 아 닌 지 순서대로 판단 하고, 만약 그렇다면 해당 번호 에 1 을 더 해 번호 가 N 이 될 때 까지 우리 가 원 하 는 축 수 를 말한다.
방법 1: 추 수의 정의 에 따 르 면 추 수 는 2, 3, 5 로 만 나 눌 수 있 기 때문에 한 수 를 2 로 나 눌 수 있다 면 2 로 연속 나 눌 수 있 고 3 으로 나 눌 수 있 으 면 3 으로 연속 나 눌 수 있 으 며 5 로 나 눌 수 있 으 면 5 로 연속 나 눌 수 있다.만약 마지막 에 얻 은 결과 가 1 이 라면, 이 수 는 정수 이 고, 그렇지 않 으 면 그렇지 않다.따라서 하나의 함 수 를 통 해 이 수가 추 수 인지 아 닌 지 를 판단 한 다음 에 해당 하 는 위치의 숫자 를 두루 찾 으 면 된다.

class Solution1{
   ///            ，           
   public int GetUglyNumber(int index){
       if (index <= 0)
           return 0;

       int number = 0;                         //     ，         
       int uglyNumber = 0;                     //     

       //              index  ，    
       while (uglyNumber < index) {
           number++;
           if (IsUgly(number))
               uglyNumber++;
       }

       return number;
   }

   ///             ，     2、3、5  ，        1，    
   public bool IsUgly(int number){
       //  2  ，     2
       while (number % 2 == 0)
           number /= 2;
       //  3  ，     3
       while (number % 3 == 0)
           number /= 3;
       //  5  ，     5
       while (number % 5 == 0)
           number /= 5;
       //          1，          ，   ，     
       return number == 1 ? true : false;
   }
}

장단 점: 방법 이 매우 직관 적 이 고 1500 을 입력 하면 1500 번 째 추 수 를 얻 을 수 있 으 며 코드 도 매우 간결 하 다.그러나 가장 큰 문 제 는 계 산 량 이 너무 많 고 시간 효율 이 높 지 않다 는 것 이다. 모든 숫자 가 추 한 숫자 든 아니 든 우 리 는 잉여 와 나 누 기 작업 을 하기 때문에 새로운 더 좋 은 알고리즘 을 찾 아야 한다.이런 방법 은 시간 효율 이 뛰 어 나 면접 관 들 이 이런 답 에 만족 하지 않 는 다.그래서 우 리 는 복잡 도가 더 낮은 해법 이 필요 하 다.
방법 2: 캐 시 배열 을 추가 로 정의 하고 추 수 를 저장 하여 생각 을 바 꿉 니 다. 우 리 는 추 수 만 추구 하고 추 수 를 상관 하지 않 습 니 다.모든 추 수 는 반드시 그 보다 작은 추 수 곱 하기 2, 3 또는 5 로 얻 을 수 있다. 그러면 우 리 는 구 하 는 추 수 를 모두 보존 하고 이전의 추 수 를 각각 2, 3, 5 로 곱 하여 이 세 가지 가장 작고 현재 의 최대 추 수의 값 보다 큰 것 을 찾 아 낸다. 즉, 다음 에 우리 가 구 해 야 할 추 수 이다.이런 방법 은 공간 으로 시간 을 바 꾸 고 시간 복잡 도 는 O (n) 이다.
3 개의 변 수 를 사용 하여 추적 하 는 기술 을 주의 하 십시오. t2 는 이 위치 이전의 수 를 모두 2 로 곱 한 것 을 나타 냅 니 다. t3 은 이 위치 이전의 수 를 모두 3 으로 곱 한 것 을 나타 냅 니 다. t5 는 이 위치 이전의 수 를 모두 5 로 곱 한 것 을 나타 냅 니 다.

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        if(index == 1)
            return 1;
        int t2 = 0, t3 = 0, t5 = 0;
        int [] res = new int[index];
        res[0] = 1;
        for(int i = 1; i

첫 번 째 사고 에 비해 두 번 째 사 고 는 추 하지 않 은 정수 에서 어떠한 계산 도 할 필요 가 없 기 때문에 시간 효율 이 현저히 향상 된다.그러나 두 번 째 알고리즘 은 이미 생 성 된 추 수 를 저장 해 야 하기 때문에 하나의 배열 이 필요 하여 공간 소 모 를 증가 시 켰 다.1 천 500 번 째 축 수 를 구 하려 면 1 천 500 개의 정 수 를 수용 할 수 있 는 배열 을 만 들 고, 이 배열 은 6KB 의 콘 텐 츠 공간 을 차지한다.첫 번 째 사고방식 은 이런 메모리 비용 이 없다.전체적으로 보면 두 번 째 사고방식 은 비교적 작은 공간 소모 로 시간 효율 의 향상 을 바 꾸 는 것 과 같 아서 비교적 좋다.
여기 서 언급 한 것 은 하드웨어 의 발전 은 무어 의 법칙 에 따라 메모리 의 용량 은 대체적으로 18 개 월 마다 두 배로 증가 하고 메모리 의 용량 이 신속하게 증가 하기 때문에 소프트웨어 개발 과정 에서 일정한 공간 을 희생 하여 시간 성능 을 최적화 하 는 방법 을 허용 하여 소프트웨어 의 응답 시간 을 최대한 단축 시 키 는 것 이다.즉 알고리즘 에서 길 게 언급 된 '공간 교환 시간' 이다.