정수에서 고유 한 자릿수를 계산하는 가장 효율적인 방법은 무엇입니까

Question

숫자의 범위는 1에서 10 입니다. 이 코드를 사용하고 있지만 시간이 없습니다.

int distinct(long long int a) 
{ 
    int ele[10]={0},i,c=0; 

    if(a==0) return 1; 
    if(a<0) a=a*-1; 

    while(a) 
    { 
     int t=a%10; 
     ele[t]=1; 
     a=a/10; 
    } 

    for (i=0;i<10;i++) 
     if (ele[i]) 
      c++; 

    return c; 
} 

Answer 1

다양한 아이디어를 통합하고 UB를 해결합니다.

IMO, 느린 속도의 중요한 원인 인 OP가 빠뜨린 것 같아요. 영업 이익

// 1 to 10^15 only 
int distinct_fast(long long int a) { 
    int ele[10]={0},i,c=0; 

    do { 
    ele[a%10]=1; 
    a /= 10; 
    } while(a); 

    i=10-1; 
    do { 
    c += ele[i]; // @barak manos 
    } 
    } while (i-- > 0); 
    return c; 
} 

// entire unsigned long long range method 1 
int distinct_complete1(unsigned long long int a) { 
    ... // same code as above 

// entire long long range method 2 
int distinct_complete2(long long int a) { 
    int ele[10]={0},i,c=0; 

    // Use (-) numbers as there are more (or the same) number of (+) numbers 
    if (a > 0) a = -a; 

    do { 
    ele[-(a % 10)] = 1; 
    a /= 10; 
    } while(a); 

    // same as above 
    ... 

---

아이디어 탐험 :

unsigned char ele[10]={0}; // smaller flags 

합니다.

do { 
    if (ele[a%10]++ == 0) c++; 
    a /= 10; 
} while(a); 
// This eliminates need for following loop to add `ele[]` 

.

// Invoke some strategy so when when a is small enough, 
// use `long` ops rather than `long long` 
if (a > 1000000000) { 
    for (i=6; i-- > 0;) { 
    if (ele[a%10]++ == 0) c++; 
    a /= 10; 
    } 
} 
unsigned long b = a; 
do { 
    if (ele[b%10]++ == 0) c++; 
    b /= 10; 
} while(b); 

.

int distinct_complete3(unsigned long long int a) { 
    unsigned char ele[10]={0}; 
    int c = 0; 
    do { 
    if (ele[a%10]++ == 0) c++; 
    a /= 10; 
    } while(a); 
    return c; 
} 

Answer 2

몇 가지 최적화 : 당신이 일반적으로 훨씬 더 빨리, 곱셈에 대한 모듈을 거래 할 수

• : q= a/10; m= a - 10 * q;

• 당신이 모든 플래그를 포장하여 최종 계산 루프를 방지 할 수 있습니다 단일 정수, let mask; mask= 0으로 초기화하십시오. 숫자 (m)를 찾을 때마다 mask|= (1 << m)으로 플래그를 지정하십시오. 결국 카운트는 bits[mask]에 의해 주어지며, 여기서 bits은 0에서 1023=2^10-1까지의 모든 정수에 대한 사전 계산 된 카운트를 포함하는 벡터입니다.

  int distinct(long long int a) 
  { 
      int mask= 0; 
      while (a) 
      { 
       int q= a/10, m= a - 10 * q; 
       mask|= 1 << m; 
       a= q; 
      } 
  
      static short bits[1024]= { 0, 1, 1, 2, 1, 2, 2, 3, ...}; // Number of bits set 
      return bits[mask]; 
  } 
  

더 나은, 당신이 그룹에서 숫자로 작업 할 수 있습니다, 세 가지의 말한다. 기본 10으로 변환하는 대신 기본 1000으로 변환하십시오. 그리고 모든 기본 1000 "숫자"에 대해 구성 십진수를 플래그하는 해당 마스크를 계산하십시오 (예 : 535은 마스크 1<<5 | 1<<3 | 1<<5 = 40을 산출 함).

약 3 배 빨라야합니다. 어쨌든, 주요 트리플에 대한 마스크 (예 : ..1 대 001)를 구분하여 앞에 오는 0을 처리해야합니다.

int distinct(long long int a) 
    { 
     int mask= 0; 
     while (true) 
     { 
      int q= a/1000, m= a - 1000 * q; 
      if (q == 0) 
      { 
       static short leading[1000]= { 1, 2, 4, 8, 16, 32, 64, ...}; // Mask for the leading triples 
       mask|= leading[m]; 
       break; 
      } 
      else 
      { 
       static short triple[1000]= { 1, 3, 5, 9, 17, 33, 65, ...}; // Mask for the ordinary triples 
       mask|= triple[m]; 
       a= q; 
      } 
     } 

     static short bits[1024]= { 0, 1, 1, 2, 1, 2, 2, 3, ...}; // Number of bits set 
     return bits[mask]; 
    } 

정적 배열을 사용하여 한 번만로드됩니다.