검 지 offer 시리즈 의 31: 배열 을 최소 로 배열 합 니 다.
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
결과 에 따 르 면 가장 작은 숫자 라 는 것 은 사실상 배열 의 모든 요소 에 대한 조합 이다.모든 요소 의 전체 배열 을 구하 고 모든 배열 의 값 의 크기 를 정렬 하면 가장 작은 수 를 얻 을 수 있다.전체 배열 을 구 하 는 알고리즘 은 이미 이전의 글 에서 언급 되 었 다.그럼 또 다른 아이디어 가 있 지 않 나 요?자바 라 이브 러 리 함수 중 sort 방법 이 있 습 니 다. 직접 사용 할 수 있 지 않 습 니까?(이 sort 방법의 시간 복잡 도 는 O (nlogn) 이기 때문에 시간 복잡 도 에 대한 요구 가 있 으 면 이 알고리즘 은 사용 할 수 없습니다.배열 을 하나의 문자열 배열 로 바 꿀 수 있 습 니 다. 이렇게 처리 하 는 것 이 편리 하기 때문에 모든 요 소 를 문자열 배열 에 추가 하고 모든 요 소 를 정렬 할 수 있 습 니 다. 마지막 으로 출력 결 과 는 가장 작은 숫자 입 니 다.
다음은 이러한 사고방식 을 바탕 으로 하 는 실현 코드 (이미 우 객 AC 에 의 해) 입 니 다.
package com.rhwayfun.offer;
import java.util.Arrays;
import java.util.Comparator;
public class PrintMinNumberofArray {
public String PrintMinNumber(int [] numbers) {
if(numbers == null || numbers.length <= 0) return "";
StringBuilder sb = new StringBuilder();
String[] str = new String[numbers.length];
int index = 0;
for(int i : numbers) str[index++] = i + "";
Arrays.sort(str, new Comparator<String>() {
public int compare(String o1, String o2) {
return (o1+o2).compareTo(o2+o1);
}
});
for (int i = 0; i < str.length; i++) {
sb.append(str[i]);
}
return sb.toString();
}
public static void main(String[] args) {
String s = new PrintMinNumberofArray().PrintMinNumber(new int[]{3,32,321});
System.out.println(s);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.