剑指Offer——把数组排成最小的数

题目描述:

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

 

输入:
输入可能包含多个测试样例。
对于每个测试案例,输入的第一行为一个整数m (1<=m
<=100)代表输入的正整数的个数。
输入的第二行包括m个正整数,其中每个正整数不超过10000000。

 

输出:
对应每个测试案例,
输出m个数字能排成的最小数字。

 

样例输入:

3
23 13 6
2
23456 56

 

样例输出:

13236
2345656

题目描述:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 

题目描述:

解题思路:

  首先,最普通的思路就是权进行一次排列,找出最小的数。但是这样可能会超时。

 

  这里,我们首先对数列进行排序,最后进行一次整合。算法上面主要采取冒泡排序,对每个数与其前面的数进行比较。

void bubbleSort(char c[][10],int n){
    int i,j;
    for( i=n-1 ; i>0 ; i-- ){
        for(j = n-1;j>(n-1-i);j--){
            if(findSmall(c,j))
                swap(c,j,j-1);
        }
    }
}

 

 

在比较时,采用特别的思路—-把两个字符串进行拼接,如果字符串1排在前面的数小,那么就把字符串1放到前面。

int findSmall(char c[][10],int i){
    char stri[20];
    char strj[20];
    strcpy(stri,c[i]);
    strcpy(strj,c[i-1]);
    strcat(stri,c[i-1]);
    strcat(strj,c[i]);
    int k;
    int length = strlen(stri); 
    for(k=0;k<length;k++){
        if(stri[k] == strj[k])
            continue;
        else if(stri[k] < strj[k]){
            return 1;
        }else{
            return 0;
        }
    }
}

 

排序后,可以保证直接进行连接的数列是最小的。

输入:

输入可能包含多个测试样例,对于每个测试案例,

输入的第一行为一个整数n(1<=
n<=1000000):代表旋转数组的元素个数。

输入的第二行包括n个整数,其中每个整数a的范围是(1<=a<=10000000)。

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

全部代码:

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bubbleSort(char c[][10],int n);
int findSmall(char c[][10],int i);
void swap(char c[][10],int i,int j);
int main(){
    int n,i;
    while(scanf("%d",&n)!=EOF && n>0 && n<=100 ){
        int arr[100];
        char c[100][10];
        char string[1000];
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
            sprintf(c[i],"%d",arr[i]);
        }
        bubbleSort(c,n);
        strcpy(string,c[0]);
        for(i=1;i<n;i++){
            strcat(string,c[i]);
        }
        printf("%s\n",string);
    }
    return 0;
}
void bubbleSort(char c[][10],int n){
    int i,j;
    for( i=n-1 ; i>0 ; i-- ){
        for(j = n-1;j>(n-1-i);j--){
            if(findSmall(c,j))
                swap(c,j,j-1);
        }
    }
}
int findSmall(char c[][10],int i){
    char stri[20];
    char strj[20];
    strcpy(stri,c[i]);
    strcpy(strj,c[i-1]);
    strcat(stri,c[i-1]);
    strcat(strj,c[i]);
    int k;
    int length = strlen(stri); 
    for(k=0;k<length;k++){
        if(stri[k] == strj[k])
            continue;
        else if(stri[k] < strj[k]){
            return 1;
        }else{
            return 0;
        }
    }
}
void swap(char c[][10],int i,int j){
    char tmp[10];
    int k;
    for(k=0;k<10;k++){
        tmp[k] = c[i][k];
        c[i][k] = c[j][k];
        c[j][k] = tmp[k];
    }
}
/**************************************************************
    Problem: 1504
    User: xhalo
    Language: C
    Result: Accepted
    Time:320 ms
    Memory:916 kb
****************************************************************/

 

 

 

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,…

输出:

对应每个测试案例,

输出旋转数组中最小的元素。 

分析:

样例输入:

5
3 4 5 1 2

 排序的变形。

样例输出:

1 

自定义比较函数:

解题思路:

  首先注意题目的要求,是递增数组的旋转数组。这怎么理解呢?

  比如,数组1 2 3 4
5,经过旋转可以旋转成为 2 3 4 5 1,或者 3 4 5 1 2 或者 1 2 3 4 5 或者 5
1 2 3 4等等。

  说的更复杂点,这其中的数字可以重复,那么数组
0 0 1 1 1 1 就可以旋转成为 1 1 1 0 0 1或者 1 1 1 1 0 0
等等,考虑到这些复杂的情况,那么就好处理了。

  这里最简单,也是钻空子的一种方式,就是在你输入数据的时候,直接检查,找出最小值。这种情况也是可以AC的。

  正常的解题思路,我们不能挨个遍历,这就显得不够高大上了,二典型的缩小时间复杂度的方法,就是二分查找了。但是考虑到一种特殊的情况,比如1
0 1 1 1是 0 1 1 1
1的旋转数组,此时进行二分,头尾中间都是1,这怎么判断呢?那么我们就两遍都进行一次查找,最后的结果进行一次比较就可以了。这样明显可以缩小时间复杂度。

比较3和32:

钻空子的代码:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int arr[1000000];
int main(void){
    int i,n;
    while(scanf("%d",&n)!=EOF && n>=1 && n <= 1000000){
        memset(&arr,0,sizeof(int)*1000000);
        int smallest = 10000001;
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
            if(smallest > arr[i])
                smallest = arr[i];
        }
        printf("%d\n",smallest);
    }
    return 0;
}
/**************************************************************
    Problem: 1386
    User: xhalo
    Language: C
    Result: Accepted
    Time:1000 ms
    Memory:4820 kb
****************************************************************/

将3和32拼接在一起为332,将32和3拼接在一起为323,比较这两个数的大小332>323,那么32应该排在3的前面。

正常的解题思路:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int arr[1000000];
int binarySearch(int *arr,int front,int rear);
int main(void){
    int i,n;
    while(scanf("%d",&n)!=EOF && n>=1 && n <= 1000000){
        memset(&arr,0,sizeof(int)*1000000);
        int smallest = 10000001;
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        printf("%d\n",binarySearch(arr,0,n-1));
    }
    return 0;
}
int binarySearch(int *arr,int front,int rear){
    if(front+1 == rear || front == rear)
        return arr[rear]<arr[front]?arr[rear]:arr[front];
    int index = (front+rear)/2;
    if(arr[front] == arr[index] && arr[rear] == arr[index]){//此时两边中间都一样,考虑到特殊情况,我们两遍均遍历一次,进行最后的比较大小。
        int find1 = binarySearch(arr,front,index);
        int find2 = binarySearch(arr,index+1,rear);
        return find1<find2?find1:find2;
    }else if(arr[index] >= arr[front] && arr[index] > arr[rear])
        binarySearch(arr,index,rear);
    else
        binarySearch(arr,front,index);
}
/**************************************************************
    Problem: 1386
    User: xhalo
    Language: C
    Result: Accepted
    Time:990 ms
    Memory:4820 kb
****************************************************************/

 

其他数类似。。

代码:

 1 class Solution {
 2 public:
 3     string PrintMinNumber(vector<int> numbers) {
 4         int numSize = numbers.size();
 5         string s;
 6         if(numSize == 0) return s;
 7         sort(numbers.begin(), numbers.end(), cmp);
 8         for(int i = 0; i < numSize; i++) {
 9             s += to_string(numbers[i]);
10         }
11         return s;
12     }
13     static bool cmp(int a, int b) {
14         string a2s = to_string(a);
15         string b2s = to_string(b);
16         string s1 = a2s + b2s;
17         string s2 = b2s + a2s;
18         return s1 < s2;
19     }
20 };

 

相关文章