알고리즘 인터뷰에서 면접관은 항상 링크 된 목록, 분류, 이진 나무 및 이진 검색 주위에 기사를 만들고 싶어하며 대부분의 사람들은 전문 서적을 따라 암기 할 수 있습니다. 면접관은 좋은 메모리 기술로 프로그래머를 모집하고 싶지 않지만 배우고 적용 할 수 없습니다. 따라서 문제를 수학적으로 모델링하고 분석하고 합리적인 알고리즘이나 데이터 구조를 사용하여 문제를 해결하는 것이 매우 중요합니다.
인터뷰 질문 : 회전 배열의 최소 수를 인쇄
제목 : 배열의 첫 몇 가지 요소를 배열 끝으로 이동하여 배열의 회전이라고합니다. 점진적으로 정렬 된 배열의 회전을 입력하고 회전 배열의 최소 요소를 출력하십시오. 예를 들어, 배열 {3, 4, 5, 1, 2}는 배열 {1, 2, 3, 4, 5}의 회전이며 배열의 최소값은 1입니다.
이 요구 사항을 달성하려면 배열을 가로 지르고 가장 작은 값을 찾고 루프를 직접 종료하면됩니다. 코드 구현은 다음과 같습니다.
public class test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {새로운 runtimeexception ( "입력 오류!"); } int result = nums [0]; for (int i = 0; i <nums.length -1; i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1]; 부서지다; }} 반환 결과; } public static void main (String [] args) {// 일반적인 입력, 단조로운 오름차순 배열 int [] array1 = {3, 4, 5, 1, 2}의 회전; System.out.println (getthemin (array1)); // 중복 숫자와 가장 작은 숫자 int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // 중복 숫자가 있지만 중복 숫자는 첫 번째 및 마지막 숫자가 아닙니다 int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // 중복 숫자가 있으며, 중복 숫자는 첫 번째 및 마지막 숫자 int [] array4 = {1, 0, 1, 1, 1}입니다. System.out.println (getthemin (array4)); // 모노톤 오름차순 배열, 0 요소를 회전시킵니다. System.out.println (getthemin (array5)); // 배열 int [] array6 = {2}에 숫자가 하나뿐입니다. System.out.println (getthemin (array6)); // 배열의 숫자는 동일한 int [] array7 = {1, 1, 1, 1, 1, 1, 1}입니다. System.out.println (getthemin (array7)); }}인쇄 결과에는 아무런 문제가 없습니다. 그러나이 방법은 분명히 최고가 아닙니다. 더 나은 방법을 찾는 방법이 있는지 살펴 보겠습니다.
순서대로 검색해야합니까?
이 두 키워드를 찾으면 필연적으로 바이너리 검색 방법을 생각할 것입니다. 그러나 많은 친구들이 우리의 배열이 더 이상 회전 후에 진정으로 주문 된 배열이 아니라고 요청할 것입니다. 그러나 두 개의 증분 배열의 조합과 같습니다. 우리는 이렇게 생각할 수 있습니다.
두 개의 위시를 낮게 및 높게 설정하고 Mid = (Low + High)/2를 설정할 수 있으며 배열 중간에서 자연스럽게 요소 배열 [중간]을 찾을 수 있습니다. 중간 요소가 앞쪽의 증분 배열에 있으면 저하 스크립트의 해당 요소보다 크거나 동일해야합니다. 현재 배열에서 가장 작은 요소는 요소 뒤에 있어야합니다. 낮은 첨자를 중간 요소로 가리킬 수있어 검색 범위를 좁힐 수 있습니다.
유사하게, 중간 요소가 후속 증분 서브 어레이에 위치한 경우, 높은 첨자에 해당하는 요소보다 작거나 같아야합니다. 이때 배열에서 가장 작은 요소는 중간 요소 앞에 있어야합니다. 높은 첨자를 중앙 첨자로 업데이트 할 수 있으며 검색 범위를 좁힐 수도 있습니다. 이동 후 높은 첨자에 해당하는 요소는 여전히 후속 증분 서브 어레이에 있습니다.
낮거나 높은 업데이트에 관계없이 검색 범위는 원본의 절반으로 줄어 듭니다. 다음으로 업데이트 된 첨자를 사용하여 새로운 검색 라운드를 반복합니다. 마지막 두 개의 위시가 인접 해있을 때까지, 즉 루프 엔드 조건이 있습니다.
나는 많은 말을했고, 나는 엉망인 것 같습니다. 질문의 입력을 사용하여 알고리즘을 시뮬레이션하고 확인할 수도 있습니다.
코드를 사용하여 Java 에서이 아이디어를 구현하는 방법을 살펴 보겠습니다.
public class test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {새로운 runtimeexception ( "입력 오류!"); } // 요소가 하나만 있으면 직접 반환하면 (nums.length == 1) nums를 반환합니다 [0]; int result = nums [0]; int low = 0, high = nums.length -1; int Mid; // 하위 스크립트에 해당하는 값이 왼쪽의 증분 서브 어레이에 있는지 확인하고 오른쪽의 숫자 서브 어레이에 있습니다 (nums [low]> = nums [high]) {// (High -Low == 1) {leture nums [high] 인 경우 루프 조건의 끝을 확인하십시오. } // 중간 위치를 중간에 가져갑니다 = (Low + High) / 2; // 중간 요소가 왼쪽에서 증가 함을 나타냅니다. } else {high = mid; }} 반환 결과; } public static void main (String [] args) {// 일반적인 입력, 단조로운 오름차순 배열 int [] array1 = {3, 4, 5, 1, 2}의 회전; System.out.println (getthemin (array1)); // 숫자를 반복하는 중복 숫자와 가장 작은 숫자는 int [] array2 = {3, 4, 5, 1, 1, 2}입니다. System.out.println (getthemin (array2)); // 중복 숫자가 있지만 중복 숫자는 첫 번째 및 마지막 숫자가 아닙니다 int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // 중복 숫자가 있고, 중복 숫자는 정확히 첫 번째 및 마지막 숫자 int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // 단조로운 오름차순 배열, 0 요소를 회전시킵니다. System.out.println (getthemin (array5)); // 배열 int [] array6 = {2}에 숫자가 하나뿐입니다. System.out.println (getthemin (array6)); // 배열의 숫자는 동일한 int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}입니다. System.out.println (getthemin (array7)); // 특별한 나는 int [] array8 = {1, 0, 1, 1, 1}를 움직이는 방법을 모른다; System.out.println (getthemin (array8)); }}앞에서 회전 배열에서 점진적으로 정렬 된 배열의 여러 숫자가 배열 뒤에서 이동되기 때문에 첫 번째 숫자는 항상 마지막 숫자보다 크거나 동일하며 0 요소가 이동하는 또 다른 특수 사례가 있습니다. 즉, 배열 자체는 자체 회전 어레이입니다. 이 상황 자체가 주문되므로 첫 번째 요소를 반환하면 결과를 NUMS [0]에 할당하는 이유입니다.
위의 코드가 완벽합니까? 우리는 시험 사례를 통해 요구 사항을 충족하지 못했습니다. Array8 입력을 자세히 살펴 보겠습니다. 먼저 컴퓨터 작업을 분석하겠습니다.
그러나 우리는 최소값이 1이 아니라 0이 아니라는 것을 알 수 있으므로 배열 [낮음], 배열 [중간] 및 배열 [High]이 동일 할 때 프로그램은 이동 방법을 모릅니다. 현재 이동 방법에 따르면, 배열 [중간]은 기본적으로 왼쪽에 증가합니다. 이것은 분명히 무책임합니다.
코드를 수정합시다.
public class test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {새로운 runtimeexception ( "입력 오류!"); } // 요소가 하나만 있으면 직접 반환하면 (nums.length == 1) nums를 반환합니다 [0]; int result = nums [0]; int low = 0, high = nums.length -1; int mid = low; // 하위 스크립트에 해당하는 값이 왼쪽의 증분 서브 어레이에 있는지 확인하고 오른쪽의 숫자 서브 어레이에 있습니다 (nums [low]> = nums [high]) {// (High -Low == 1) {leture nums [high] 인 경우 루프 조건의 끝을 확인하십시오. } // 중간 위치를 중간에 가져갑니다 = (Low + High) / 2; // 세 값이 동일한 특수 경우에서 처음부터 끝까지 가장 작은 값을 찾아야합니다. } // 중간 요소가 왼쪽에서 증가 함을 나타냅니다. } else {high = mid; }} 반환 결과; } / *** 배열에서 최소값을 찾으십시오* @param nums 배열* @param 시작 배열 시작 위치* @param 끝 배열 엔드 위치* @return 발견* / public static int midinorder (int [] nums, int start, int end) {int result = nums [start]; for (int i = start+1; i <= end; i ++) {if (result> nums [i]) result = nums [i]; } 반환 결과; } public static void main (String [] args) {// 일반적인 입력, 단조로운 오름차순 배열 int [] array1 = {3, 4, 5, 1, 2}의 회전; System.out.println (getthemin (array1)); // 중복 숫자와 가장 작은 숫자는 가장 일반적인 숫자 int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // 중복 숫자가 있지만 중복 숫자는 첫 번째 및 마지막 숫자가 아닙니다 int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // 중복 숫자가 있고, 중복 숫자는 정확히 첫 번째 및 마지막 숫자 int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // 단조로운 오름차순 배열, 0 요소를 회전시킵니다. System.out.println (getthemin (array5)); // 배열 int [] array6 = {2}에 숫자가 하나뿐입니다. System.out.println (getthemin (array6)); // 배열의 모든 숫자는 동일한 int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); // 특별한 나는 int [] array8 = {1, 0, 1, 1, 1}를 움직이는 방법을 모른다; System.out.println (getthemin (array8)); }}그런 다음 완전한 테스트 사례와 테스트 패스를 사용하여 넣습니다.
요약
실제로,이 질문에는 조사해야 할 많은 요점이 있지만 실제로 이진 검색의 유연한 적용을 조사하는 것입니다. 많은 친구들은 이진 검색 아이디어를 배우지 않고 순서대로 바이너리 검색을 기억해야하며, 이는 원형 검색 최소값에 대해서만 생각하게됩니다.
많은 친구들이 인터뷰 중에 Android Original Ecosystem이 기본적으로 일반적인 알고리즘을 캡슐화하고 인터뷰에서 이러한 비효율적 인 알고리즘에 항의했다는 성명을 발표했습니다. 이것은 실제로 꽤 바보입니다. 우리는 Rote 알고리즘을 구현하려고하지 않지만 영리한 아이디어를 배우려고합니다. 생각 능력을 지속적으로 개선함으로써 만 더 나은 경력 개발을 얻는 데 도움이 될 수 있습니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.