【剑指offer】-把数组排成最小的数-33/67

本是古典何须时尚 2023-02-23 01:25 71阅读 0赞

# 1. 题目描述 #

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

# 2. 题目描述 #

1.  题目的意思：给你一个数组，要求你返回一个字符串，为这些数组中最小的数（字符串）
2.  我们需要对数组内的数字进行排序，这里进行的排序指的是对其在数组内的位置进行排序，这里我们需要一个规则，如果NM > MN，则N>M；这里的大于不是常规的大于关系，是我们自己定义的一个关系
3.  将数组依次存入ArrayList中，对于ArrayList进行排序，可以选择的排序方式有：冒泡排序、快速排序、重写排序方法
4.  最终利用StringBuilder的toString的方法，得到最终的结果

# 3. 题目代码 #

public class Test35 {
        
    	public static void main(String[] args) {
        
    		int[] nums = new int[] {
         3, 30, 34, 5, 9 };
    		System.out.println(PrintMinNumber(nums));
    	}
    
    	public static String PrintMinNumber(int[] numbers) {
        
    		ArrayList<String> list = new ArrayList<>();
    		for (int i = 0; i < numbers.length; i++) {
        
    			list.add(String.valueOf(numbers[i]));
    		}
    		// for (int i = 0; i < list.size() - 1; i++) {
        
    		// for (int j = 0; j < list.size() - i - 1; j++) {
        
    		// String string = list.get(j + 1);
    		// String string1 = list.get(j) + string;
    		// String string2 = string + list.get(j);
    		// if (string1.compareTo(string2) >= 0) {
        
    		// list.set(j + 1, list.get(j));
    		// list.set(j, string);
    		// }
    		// }
    		// }
    		kuaipai(list, 0, list.size() - 1);
    		System.out.println(list);
    		StringBuilder stringBuilder = new StringBuilder();
    		for (int i = 0; i < list.size(); i++) {
        
    			stringBuilder.append(list.get(i));
    		}
    		return stringBuilder.toString();
    	}
    
    	public static void kuaipai(ArrayList<String> list, int left, int right) {
        
    		if (left >= right) {
        
    			return;
    		}
    		int i = left;
    		int j = right;
    		String string = list.get(i);
    		while (i < j) {
        
    			while (i < j && (list.get(j) + string).compareTo(string + list.get(j)) >= 0) {
        
    				j--;
    			}
    			list.set(i, list.get(j));
    			while (i < j && (list.get(i) + string).compareTo(string + list.get(i)) <= 0) {
        
    				i++;
    			}
    			list.set(j, list.get(i));
    		}
    		list.set(i, string);
    		kuaipai(list, left, i - 1);
    		kuaipai(list, i + 1, right);
    	}
    }