안녕하세요, [A, B, C, A, B, C, A, C, B] (임의 순서)와 같은 배열이 있고 [A, A, A , B, B, C, C, C] (각 그룹이 함께 함)이며 허용되는 작업은 다음과 같습니다. 1) 배열의 i 번째 항목 을 쿼리합니다. 2) 배열에서 두 항목을 바꿉니다.배열의 항목을 그룹화 하시겠습니까?
O (n)에서 작업을 수행하는 알고리즘을 설계하는 방법은 무엇입니까?
감사합니다.
정렬 알고리즘은 새로운 (즉, 개발 프로세스의 첫 단계) 디자인이 아닙니다. 연구를해야합니다 sortalgorithms 귀하의 요구를 충족 참조하십시오.
는 (그것은 당신이 정말로 자신의 새로운 정렬 알고리즘이 필요할 수 있습니다 물론 가능하지만, 일반적으로 그 — 다른과 — requirements. 높은 특정있다)이 첫 번째 단계가 아닌 경우(하지만 돈을 그것이 사실이라고 생각하지 않는다), 당신이 이미 시도한 것과 그것이 당신에게 어떻게 실패했는지를 아는 것이 도움이 될 것입니다.
이것은 정렬과 관련이 있지만 정렬 문제는 아닙니다. 그는 O (n) 알고리즘을 사용하여 배열에서 항목을 그룹화합니다. 그룹의 순서는 중요하지 않습니다. –
실제로는 단지 counting sort입니다.
배열을 한 번 스캔하고 아이디어를 얻을 수있는 As, Bs, Cs의 수를 —으로 계산하십시오. 이것은 bucket sort —처럼 보이지는 않지만 그 라인을 따라갑니다. As Bs와 Cs의 개수는 As, Bs 및 Cs의 문자열이 어디에 속하는지에 대한 아이디어를 제공해야합니다.
'[text] (URL)'을 사용할 수 있다는 것을 알고 계셨습니까? 숙제로 태깅을 격려하여 답을 나누어 주겠다고 말한 사람에게는 호기심이 듭니다. (최근에 당신의 뻔뻔스런 rep-whoring에 대해 비판적 이었지만, 숙제 태그에 대한 최근의 공지와 적용 방법에 대해서도 마찬가지입니다. –
아니요. 그러나 질문을받습니다. 이 일을 제자리에서하라. 그래서, 그것은 제 생각과는 조금 다릅니다. –
Roger, 나는이 포럼에서 1000 RPP를 얻을 때까지 내 GF가 내놓지 않을 것이라고 썼다. 너는 그 속임수가 아니다. 또한, hw에 관하여 : 나는 그 물건을 다시 보지 않고 멋진 PHP 웹 페이지를 코딩하는 알고리즘을 사용하는 많은 사람들을 알고있다. 이 사람들이 자신의 종류를 구현할 필요가 없다고 말할 때 나를 믿어 라. –
숙제 인 경우 태그를 붙이십시오. – danben
숙제로 표시하십시오. 값 9A, B, C 등의 범위가 제한되어 있습니까?) –
O (n) space 또는 time? –