루프에 대한 두 (루프에 대한 내부 루프) 자바에서 나는 다음과 같은 한

Question

문제를 최적화하는 방법 :

• 내가 매우 긴 문자열이 String str = "abcdefghiart----"
• 지금 내가 문자열을 반복하고 싶은 싶은 먼저이 방법은 잘 작동하지만 반복 복잡성이 매우 큰 경우 문자열에 매우 높은 것입니다 만 마지막 두 문자는

• 중복 문자열

• 내가 검색 할 수있는 두 개의 for 루프를 적용하여 달성 할 수있는이을의 첫 번째 중복 문자를 찾을 수 중복 ity

  이제 복잡성을 최소화하고이 코드를 최적화하고 싶습니다. 루프도 foreach 반복 사용할 수 있지만 여전히 두 foreach 루프됩니다. 나는 어떤 시스템 라이브러리도 사용하고 싶지 않다. 누군가가 나를 도울 수 있습니까?

Answer 1

다음은 문자열에서 첫 번째 중복 문자를 찾는 방법입니다.

public static String findFirstDuplicate(String string){ 

       for(int i=0;i<string.length()-1; i++){ 
        String c=string.charAt(i)+""; 
        if(string.indexOf(c, i+1)>-1) 
         return c; 
       } 

       return null; 
    } 

최적화를 위해 최적화를 수행하면 중복 값을 찾기 위해 병합 정렬을 사용자 정의하고 중복이 발견되면 종료 할 수 있습니다. 여기에서 설명하는 것이 약간 복잡하지만 변형 된 병합 정렬 알고리즘을 사용하면 최악의 경우 O (nlogn)에서 첫 번째 중복을 찾을 수 있습니다.

Answer 2

크기 int 배열을 정의는 다음에 대응하는 알파벳 인 경우 [26]

대하여 반복 문자열을 통해 슬롯의 값이있는 경우, 각 문자 체크 각 알파벳 하나 개의 슬롯은> 0 슬롯에 중복 문자가 있습니다. 숫자가 0이면 그냥 증가시키고 앞으로 계속 이동하십시오.

Answer 3

BitSet seenCharacters = new BitSet(); 
for(int i=0;i<str.length(); i++) { 
    if(seenCharacters.get(str.charAt(i))) { 
    return str.charAt(i); // duplicate 
    } 
    seenCharacters.set(i); 
} 

... 충분히 직설적입니까?

Answer 4

나는 다른 해결책으로 문제에 접근 할 것이다. 해시 맵 (또는 그 파생물)을 사용하면 키는 문자가되고 값은 null이됩니다.

그러면 한 번에 한 문자 씩 문자열을 가로 지르고, 각 문자에 대해 해시 맵에 항목을 삽입하려고 시도합니다. 삽입에 실패하면 문자 (키 자체)가 중복임을 알 수 있습니다.