검 지 offer 시리즈 의 31: 배열 을 최소 로 배열 합 니 다.

3008 단어
제목 설명
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {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);
    }
}

좋은 웹페이지 즐겨찾기