선형 배열보다 비트 배열의 비트를 분할하는 방법

Question

최근 인터뷰 질문입니다.

---

1과 0의 배열을 감안할 때, '0'은 함께 그룹화되도록 in place 비트를 분할하는 방법을 발견하고 하나의 함께 그룹화된다. 1이 0보다 앞서거나 0이 1보다 앞서 있는지 여부는 중요하지 않습니다.

입력의 예는 101010101이고 출력은 111110000 또는 000011111입니다.

선형 시간 미만으로 문제를 해결하십시오.

문제를 간단하게 만듭니다. 입력은 정수 배열이며 각 요소는 1 또는 0입니다. 출력은 정수로 잘 분할 된 동일한 정수 배열입니다. 나에게

---

이는 O (N)에 해결 될 수 있다면 쉬운 질문이다. 내 접근 방식은 배열의 양쪽 끝에서 시작하는 두 개의 포인터를 사용하는 것입니다. 각 포인터를 늘리거나 줄입니다. 올바른 정수를 가리 키지 않으면 두 정수를 바꿉니다.

 
    int * start = array; 
    int * end = array + length - 1; 

    while (start < end) { 
     // Assume 0 always at the end 
     if (*end == 0) { 
      --end; 
      continue; 
     } 

     // Assume 1 always at the beginning 
     if (*start == 1) { 
      ++start; 
      continue; 
     } 

     swap(*start, *end); 
    } 

그러나 인터뷰에서는 하위 선형 솔루션이 있다고 주장합니다. 이것은 열심히 생각하고 있지만 여전히 대답을 얻지 못하게합니다.

누구든지이 인터뷰 질문에 도움이 될 수 있습니까?

업데이트 : : 하위 선형 시간에 문제를 해결할 수 없다는 응답을 볼 때 하위 선형 솔루션을 사용할 수 없다는 원래 생각을 확인할 수 있습니다.

면접관이 트릭을 할 가능성이 있습니까?

Answer 1

선형 시간보다 더 빨리 해결 방법이있을 수는 없습니다.

모두 1 인 비트 배열을 상상해보십시오. 모든 솔루션은 이미 배열 된 것으로 선언하기 전에이 배열의 모든 비트를 검사해야합니다. 모든 비트를 검사하는 데는 선형 시간이 필요합니다.

Answer 2

불가능합니다. 선형 시간보다 짧게하는 것은 모든 배열 요소 (바이너리 검색과 같은)를 보지 않는다는 것을 의미합니다. 그러나 배열의 어떤 요소가 무엇인지 알지 못하기 때문에 각 배열 요소를 최소한 한 번 봐야합니다.

룩업 테이블을 사용하면 더 빠르지 만 O (n/8)은 여전히 ​​O (n)이므로 조사자가 잘못되었거나 질문을 잘못 이해했습니다.

Answer 3

아마 "혼란은"선형 시간보다 적습니다 ". 예를 들어,이 솔루션은 비트 수를 계산하여 많은 비트를 포함하는 마스크를 만듭니다. 이 계산 비트의 수를 최소화하더라도

// from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan 
unsigned count_bits(unsigned pX) 
{ 
    unsigned result; 
    for (result = 0; v; ++result) 
    { 
     pX &= pX - 1; 
    } 

    return result; 
} 

unsigned n = /* the number */; 

// r contains 000...111, with number of 1's equal to number of 1's in v 
unsigned r = 1 << count_bits(n); 

, 그것은 여전히 ​​선형입니다 :에 비트 헤아릴이 있지만 그것은 단지 비트를 계산합니다. 따라서 이것이 "선형 선형"이 의미하는 것이라면 거기에 가야합니다.

그러나 대수적 또는 상수 적으로 서브 선형이라는 것을 실제로 의미한다면, 나는 방법을 보지 못합니다.당신은 모든 값에 대해 룩업 테이블을 만들 수는 있지만,/

Answer 4

다른 사람들이 말했듯이, 나는 이것이 선형 시간보다 짧아 질 수 있다고 생각하지 않습니다.

int a1[8] = {1,0,1,0,1,0,1,0}; 
std::fill(std::remove(a1, a1+8, 0), a1+8, 0); 

Answer 5

기술적으로는 별도의 프로세서로 배열의 각 요소를 보낼 수 다음 선형 시간 이내에 그것을 : 선형 시간 솔루션의 경우,이 같은 자신의 루프 대신 알고리즘을 STL 수 있습니다. N 개의 프로세서를 가지고 있다면, O (1) 시간 안에 그것을 할 수도 있습니다!

Answer 6

그것은 당신이 충분한 메모리가 주어진 선형 시간에 빨리 다음 수 있습니다, 그것은 O (1)

분할 된 비트 마스크에 매핑되는 벡터의 인덱스로 비트 마스크를 사용하여 수행 할 수 있습니다.

예제를 사용하면 색인 341 (101010101)에서 값 496 (111110000)이 저장됩니다.

Answer 7

음 .. '선형 미만'시간 (건방진 방법)을 수행 할 수 있습니다.

if(n % 2) 
{ 
    // Arrange all 1's to the right and DON'T check the right-most bit, because it's 1 
}else{ 
    // Arrange all 0's to the right and DON'T check the right-most bit, because it's 0. 
} 

그래서, 기술적으로는 '그룹'선형 시간 이하의 비트 : P 나에게

Answer 8

, 가장 가능성있는 해석은 다음과 같습니다 비트에 있어야하는

• 배열 대신 int를 사용하면이 경우 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan 또는 8 비트 (이상) 조회 테이블을 사용할 수 있습니다.

• "sublinear"는 O 미만 (n)보다 "n보다 작음"을 의미합니다. 그러나 그것도 아래에 열거 된 것과 같은 이유로 불가능한 것처럼 보입니다.

• 배열의 모든 요소가 답을 결정하기 위해 검토해야하기 때문에 그렇지 않으면 문제는, 잘못된 질문

• 또 다른 오해가있다, 그것은 적어도 'n'을 운영한다. 하나 개의 단어를 처리 할 때 0 또는 최초의 1 초, 오히려 bools보다는 비트에 대한 참조 중 하나를 목록

은, 비록, 내가 첫 번째 옵션과 같은 의도 된 생각하게, 아주 많이하지 않습니다 차. 나는 면접관이 실제로 염두에두고있는 것을 알고 싶다.

Answer 9

병렬 처리 중이 작업을 분할하는 것은 병렬 처리가 문제 크기보다 느리게 증가한다고 가정 할 경우에만 N/M (또는 O (N))의 비용이 들게됩니다. 지난 10 년 동안 (GPU를 통한) 평행선 현상은 전형적인 문제 크기보다 더 빠르게 증가하고 있으며, 이러한 추세는 앞으로도 계속 될 것으로 보입니다. GPU 및 클라우드 컴퓨팅의 진보는 시간이 지남에 따라 그러한 문제를 제공하기 때문에 광범위한 문제에 대해서는 "무한 병렬 처리"또는보다 정확하게 "예상되는 문제 크기보다 큰 병렬 처리"를 가정하는 것이 좋습니다. 필요한 부가 조작자가 결합 모두 0과 1 비트를 추가 할 수 있기 때문에

무한 평행이 문제가 O (logN) 시간이 해결 될 수 있다고 가정하면, 그리고 그것은 적어도 logN 시간에서 단계에 필요 완전한.