검지 Offer 면접 문제 33 (자바 버 전): 배열 을 최소 화 합 니 다.

제목: 정수 배열 을 입력 하고 배열 안의 모든 숫자 를 하나의 숫자 로 연결 하여 연결 할 수 있 는 모든 숫자 중 하 나 를 인쇄 합 니 다.예 를 들 어 배열 (3, 32, 321 곶 을 입력 하면 이 3 개의 숫자 가 배열 할 수 있 는 최소 숫자 321323 을 출력 합 니 다.
이 문제 의 가장 직접적인 방법 은 먼저 이 배열 의 모든 숫자의 전체 배열 을 구 한 다음 에 모든 배열 을 연결 한 다음 에 배열 한 숫자의 최소 치 를 구 하 는 것 이다.구 배열 은 면접 문제 28 과 매우 비슷 하 다.배열 에 따라 조 합 된 것 은 n 개의 숫자 가 모두 n 이다!배열, 우리 더 빠 른 알고리즘 을 다시 한 번 봅 시다.
이 문 제 는 사실 우리 가 정렬 규칙 을 찾 을 수 있 기 를 바 랍 니 다. 배열 은 이 규칙 에 따라 정렬 한 후에 가장 작은 숫자 로 배열 할 수 있 습 니 다.정렬 의 규칙 을 정 하려 면 두 개의 숫자 를 비교 해 야 한다. 즉, 두 개의 숫자 m 와 n 을 제시 해 야 한다. 우 리 는 하나의 규칙 으로 m 와 n 중 어느 것 이 앞 에 있어 야 하 는 지 를 판단 해 야 한다. 이 두 숫자의 값 만 비교 하 는 것 이 아니 라 어느 것 이 더 큰 지 를 판단 해 야 한다.
문제 의 요구 에 따라 두 개의 숫자 m 와 n 은 숫자 mn 과 nm 를 맞 출 수 있다.하면, 만약, 만약...
다음은 숫자 m 와 n 을 어떻게 맞 추 는 지, 숫자 mn 과 nm 를 어떻게 얻 고 그들의 크기 를 비교 하 는 지 를 고려 해 보 자.직접 수치 로 계산 하 는 것 은 어렵 지 않 지만 잠재 적 인 문 제 는 m 와 n 이 모두 int 가 표현 할 수 있 는 범위 내 에서 그들 을 합 친 숫자 mn 과 nm 를 int 로 표시 하면 넘 칠 수 있 기 때문에 이것 은 스텔스 의 대수 문제 이다.
대수 문 제 를 직관 적 으로 해결 하 는 방법 은 숫자 를 문자열 로 바 꾸 는 것 이다.또한, 숫자 m 와 n 을 연결 하여 mn 과 nm 를 얻 을 수 있 기 때문에, 그들의 자릿수 는 틀림없이 같 을 것 이 므 로, 그들의 크기 를 비교 하려 면 문자열 의 크기 에 따라 비교 규칙 만 있 으 면 된다.
이 사고방식 을 바탕 으로 우 리 는 코드 를 실현 한다.

/**
 *          
 *          ，                  ，
 *                   
 */
package swordForOffer;

/**
 * @author JInShuangQi
 *
 * 2015 8 9 
 */
public class E33SortArrayForMinNumber {
	
	public void printMin(int[] arr){
		int[] clone = arr.clone();
		printMinNumber(clone,0,clone.length-1);
		for(int i : clone)
			System.out.print(i);
	}
	//  +  
	public void printMinNumber(int[] arr,int left,int right){
		if(left < right){
			int main_number = arr[right];
			int small_cur = left;
			for(int j = left;jright.charAt(i))
					return false;
		}
		return result;
	}
	public static void main(String[] args){
		int arr[] = {3,32,321};
		E33SortArrayForMinNumber test = new E33SortArrayForMinNumber();
		test.printMin(arr);
	}
}