剑指offer--把数组排成最小的数（java）

旧城等待， 2021-11-02 09:00 226阅读 0赞

### 剑指offer--把数组排成最小的数 ###

三种常见解法：

1.  全排数组，列出所有可能的组合，然后找出其中最小的那一个。  
    **时间复杂度：O(n!)**
    
        TreeSet<String> str_map = new TreeSet<String>();
            public String PrintMinNumber(int [] numbers) { 
            	if(numbers==null || numbers.length == 0)
            		return "";
            	Permutation_int(numbers,0);
        		return str_map.first();
            }
        
        	private void Permutation_int(int[] numbers, int index) { 
        		if(index==numbers.length-1) { 
        			String str = changeToStr(numbers);
        			str_map.add(str);
        		}
        		for(int j=index;j<numbers.length;j++) { 
        			if(j!=index && numbers[index]== numbers[j])
        				continue;
        			swap_int(numbers, index, j);
        			Permutation_int(numbers, index+1);
        			swap_int(numbers, index, j);
        		}
        	}
        
        	private String changeToStr(int[] numbers) { 
        		StringBuffer stringBuffer = new StringBuffer();
        		for(int i=0;i<numbers.length;i++) { 
        			stringBuffer.append(numbers[i]);
        		}
        		return new String(stringBuffer);
        	}
        
        	private void swap_int(int[] numbers, int index, int j) { 
        		int temp = numbers[index];
        		numbers[index] = numbers[j];
        		numbers[j] = temp;
        	}

2.排序思想，只是顺序是按照题目的意思来排，排完之后把所有的元素拼起来就可以了。这里用的是快排。  
**时间复杂度：O(nlogn)**

public String PrintMinNumber(int [] numbers) { 
        	if(numbers==null || numbers.length == 0)
        		return "";
        	quick_sort_minNumber(numbers);
        	StringBuffer str = new StringBuffer();
        	for(int i=0;i<numbers.length;i++) { 
        		str.append(numbers[i]);
        	}
        	return new String(str);
        }
    
        private void quick_sort_minNumber(int[] numbers) { 
        	sort_minNumber(numbers, 0, numbers.length-1);
        }
    
    	private void sort_minNumber(int[] numbers, int low, int high) { 
    		if(low<high) { 
    			int SplitIndex = MySplit(numbers, low, high);
    			sort_minNumber(numbers, low, SplitIndex-1);
    			sort_minNumber(numbers, SplitIndex+1, high);
    		}
    	}
    
    	private int MySplit(int[] numbers, int low, int high) { 
    		int SplitValue = numbers[low];
    		int LowIndex = low;
    		while(low<high) { 
    			while(low<high && myCompare(numbers[high], SplitValue)==1)
    				high--;
    			while(low<high && myCompare(numbers[low], SplitValue)!=1)
    				low++;
    			if(low<high) { 
    				int temp = numbers[low];
    				numbers[low] = numbers[high];
    				numbers[high] = temp;
    			}
    		}
    		numbers[LowIndex]=numbers[low];
    		numbers[low] = SplitValue;
    		return low;
    	}
    
    	private int myCompare(int i1, int i2) { 
    		String o1 = String.valueOf(i1);
    		String o2 = String.valueOf(i2);
        	int len1 = o1.length();
    		int len2 = o2.length();
    		int maxlen = len1>len2?len1:len2;
    		if(o1.equals(o2))
    			return 0;
    		if(len1>len2) { 
    			for(int i=len2-1;i<len1-1;i++) { 
    				o2+=o2.charAt(len2-1);
    			}
    		}
    		else if(len1<len2){ 
    			for(int i=len1-1;i<len2-1;i++) { 
    				o1+=o1.charAt(len1-1);
    			}
    		}
    		for(int i=0;i<maxlen;i++) { 
    			if(o1.charAt(i)<o2.charAt(i))
    				return -1;
    		}
    		return 1;
    	}