华为机试题：整型字符串排序

雨点打透心脏的1/2处 2022-08-20 07:28 219阅读 0赞

<table style="margin:0px; padding:0px; width:970px; border:0px; border-collapse:collapse; border-spacing:0px; empty-cells:show; color:rgb(0,0,0); font-family:'Times New Roman',Arial,微软雅黑,宋体,Tahoma,Helvetica,SimSun,sans-serif,宋体"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px; height:26px"> 
   <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 描述:&nbsp;</td> 
   <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 给定字符串内有很多正整数，要求对这些正整数进行排序，然后返回排序后指定位置的正整数&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 排序要求：按照每个正整数的后三位数字组成的整数进行从小到大排序&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 1）如果不足三位，则按照实际位数组成的整数进行比较&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 2）如果相等，则按照输入字符串中的原始顺序排序&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 说明（以下内容考生无须检查，调用者保证）：&nbsp;</p> 
    <div style="margin:0px; padding:0px">
      1)&nbsp;字符串以’\0’结尾，仅包含数字、空格&nbsp; 
    </div> 
    <div style="margin:0px; padding:0px">
      2)&nbsp;字符串内正整数之间以单个空格分隔，字符串首尾没有空格&nbsp; 
    </div> 
    <div style="margin:0px; padding:0px">
      3)&nbsp;正整数格式为十进制，大小：1~1000000，正整数的数字非零开始&nbsp; 
    </div> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 示例:</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 如字符串内容</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 1223&nbsp;22&nbsp;3232&nbsp;2016</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 按照规定排序后&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 2016&nbsp;22&nbsp;1223&nbsp;3232</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 查询排序后的第3个数是&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 1223&nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

这份代码网上找的：

/******************************************************************************
    
    Copyright (C), 2001-2011, Huawei Tech. Co., Ltd.
    
    ******************************************************************************
    File Name     :
    Version       :
    Author        :
    Created       : 2011/9
    Last Modified :
    Description   :
    Function List :
    
    History       :
    1.Date        : 2011/9
    Author      :
    Modification: Created file
    
    ******************************************************************************/
    
    
    
    /*****************************************************************************
    Description   : 根据字符串内容，输出排序后指定位置的正整数
    Input Param   : input_string  输入的字符串
    			    serial_number  排序后的序列号，从1开始
    			    output_string_max_length  output_string的最大长度，包括'\0'
    Output Param  : output_string  返回指定的字符串，必须包括'\0'，内存由调用者分配和释放
    Return Value  : 成功返回0，失败返回-1（如：输入字符串是空串、输入序列号超出范围、最大长度不足）
    *****************************************************************************/
    int find_string(const char* input_string, int serial_number, int output_string_max_length, char* output_string)
    {
    
    	/* 在这里实现功能 */
    	if(!input_string||!output_string)
    		return -1;
    	char *temp,*temp1; 
    	int len=0;
    	while(input_string[len]!='\0'){
    		len++;
    	}
    	int t=0,c=0,j;
    
    	char **p=new char*[len];
    	int *num=new int[len];
    	*p=new char[len];
    	temp=*p;
    	for(int i=0;i<=len;i++){
    		if(i==len||input_string[i]==' '){
    			*temp='\0';
    			if(t<1||t>1000000)
    				return -1;
    			if(t>=1000)
    				t%=1000;
    
    			temp=*(p+c);
    			j=c;
    			for(;j>0;j--){
    				if(num[j-1]<=t)
    					break;
    				num[j]=num[j-1];
    				*(p+j)=*(p+j-1);
    			}
    			num[j]=t;
    			*(p+j)=temp;
    			t=0;
    
    			c++;
    			*(p+c)=new char[len];
    			temp=*(p+c);
    		
    		}else{
    			*temp++=input_string[i];
    			t=t*10+input_string[i]-'0';
    		}
    	}
    	if(serial_number>c)
    		return -1;
    	len=0;	
    	temp=p[serial_number-1];
    	while(*temp!='\0'){
    		temp++;
    		len++;
    	}
    	if(len>=output_string_max_length)
    		return -1;
    	temp1=output_string;
    	temp=p[serial_number-1];
    	while(*temp!='\0'){
    		*temp1++=*temp++;
    	}
    	*temp1='\0';
    
    	return 0;
    }

我自己写的提交之后超时，不知道为什么，求高手指点

#include "find_string.h"
    #include <stdlib.h>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    /*自定义比较函数*/
    bool compare(string s1, string s2)
    {
    	const char* p1 = s1.c_str();
    	const char* p2 = s2.c_str();
    
    	int d1 = atoi(p1) % 1000;
    	int d2 = atoi(p2) % 1000;
    
    	if (d1 < d2)
    	{
    		return true;
    	}
    
    	return false;
    }
    
    /******************************************************************************
    
    Copyright (C), 2001-2011, Huawei Tech. Co., Ltd.
    
    ******************************************************************************
    File Name     :
    Version       :
    Author        :
    Created       : 2011/9
    Last Modified :
    Description   :
    Function List :
    
    History       :
    1.Date        : 2011/9
    Author      :
    Modification: Created file
    
    ******************************************************************************/
    
    
    
    /*****************************************************************************
    Description   : 根据字符串内容，输出排序后指定位置的正整数
    Input Param   : input_string  输入的字符串
    			    serial_number  排序后的序列号，从1开始
    			    output_string_max_length  output_string的最大长度，包括'\0'
    Output Param  : output_string  返回指定的字符串，必须包括'\0'，内存由调用者分配和释放
    Return Value  : 成功返回0，失败返回-1（如：输入字符串是空串、输入序列号超出范围、最大长度不足）
    *****************************************************************************/
    int find_string(const char* input_string, int serial_number, int output_string_max_length, char* output_string)
    {
    
        /* 在这里实现功能 */
    	if (input_string == NULL || serial_number < 1 || output_string_max_length < 1 || output_string == NULL)
    	{
    		return -1;
    	}
    
    	char* taken = NULL;
    	char* kong = NULL;
    	
    	vector<string> vec;
    	unsigned int i = 0;
    
    	char *pstr = new char[strlen(input_string) + 1];
    	/*分离单个数字*/
    	strcpy_s(pstr, strlen(input_string) + 1, input_string);
    	pstr[strlen(input_string)] = '\0';
    
    	taken = strtok_s(pstr, " ", &kong);
    	while (taken != NULL)
    	{
    		vec.push_back(string(taken));
    		taken = strtok_s(NULL, " ", &kong);
    	}
    	
    	/*从小到大排序*/
    	sort(vec.begin(), vec.end(),compare);
    
    	if (vec.size() < (unsigned int)serial_number)
    	{
    		return -1;
    	}
    
    	if ((unsigned int)output_string_max_length <= vec[serial_number].size())
    	{
    		return -1;
    	}
    	string ss = vec[serial_number - 1];
    	for (i = 0; i < ss.size(); i++)
    	{
    		output_string[i] = ss[i];
    	}
    	output_string[i] = '\0';
    
        return 0;
    }