연결된 목록의 중복 값 식별 C++

Question

사용자의 입력 인 연결된 목록에서 어떤 값과 중복 된 값을 식별할지 알고 싶습니다. 그리고 이것은 내가 그것을 위해 쓴 코드 :

int count; 
int compare, compare2; 

    for (p = first; p != NULL; p = p->next){ 
     compare = p->num; 
     for (j = first; j != NULL; j = j->next){ 
      if (compare == j->num){ 
       compare2 = j->num; 
       count++; 
      } 
     } 
     if (count > 1){ 
      cout << "There are at least 2 identical values of: " << compare2 << " that repeat for: " << count << "times" << endl; 
     } 
    } 

는 기본적으로 그것의 아이디어는 내가 처음 루프에서 첫 번째 요소를 가지고 두 번째 루프의 모든 요소를 ​​비교하고 경우가있는 경우 계산이었다 그 (것)들의 유사 하, 결과를 인쇄하십시오 - 그 후에 다음 성분을 가지고 간다.

그러나 출력은 모든 요소이며 정확하게 계산되지 않습니다. 나는 그것을 조정하는 방법에 그냥 길을 잃었 어.

두 개의 루프에서 동일한 p 변수를 사용했지만 루프를 반복하려는 동일한 목록이므로 시도했지만 입력이 끝나자 마자 .exe가 실패했습니다.

중복 값을 삭제하는 기능이있는 곳에서 몇 가지 예를 보았지만 비교 부분은 while 루프와 함께 실행됩니다. 궁금한 점은 무엇입니까?

Answer 1

p과 j이 모두 전체 목록에서 반복되므로 논리에 결함이 있습니다. p == j 일 때 값은 일치하도록 바인딩됩니다.

변경 또한

 if (p != j && compare == j->num){ 
      compare2 = j->num; 
      count++; 
     } 

에 블록

 if (compare == j->num){ 
      compare2 = j->num; 
      count++; 
     } 

, 당신은 compare와 동일합니다 compare2 때문에 라인

  compare2 = j->num; 

필요하지 않습니다.

내부 for 루프를 조금 변경하여 테스트 수를 줄일 수 있습니다. 그런 다음 p != j 비트가 필요하지 않습니다.

for (j = p->next; j != NULL; j = j->next){ 
     if (compare == j->num){ 
      count++; 
     } 
    } 

Answer 2

문제는 당신이 (compare)와 비교하는 요소를 제외하지 않는다는 것입니다. 그래서 모든 요소에 대해 적어도 하나의 중복을 발견했습니다 - 그 자체! 내부 루프의 요소 다음에 현재 (p) 뒤에 오는 요소를 비교해보십시오.

Answer 3

귀하의 O (N * N) 방법 :

// Pick an element 
for (p = first; p != NULL && p->next !=NULL ; p = p->next) 
{ // Compare it with remaining elements 
    for (j = p->next ; j != NULL; j = j->next) 
    { 
     if (p->num == j->num) 
     {   
      count++; 
     } 
    if(cout > 1) 
    { 
     std::cout << p->num << " occurs "<< count << times << '\n' ; 
    } 
} 

그것의 더 나은이 문제를 해결하기는 HashMap을 사용하는이 O (N)이다 N 여분의 공간

와 시간

std::unordered_map<int, int> m ; 
for(p = first; p != NULL ; p = p->next) 
{ 
    m[ p->num ]++; 
} 
for (const auto &pair : m) 
{ 
    if(pair.second > 1) 
     std::cout << pair.first << ": " << pair.second << '\n'; 
}