U1002:487-3279

其实这个题目比较简单。唯一比较恶心的就是，输入字符串竟然长度为16还不够。应该来说不会无谓的输入'-'的么。输入长度扩展到80就OK了

不过这个代码数据量上升，对于一些操作性能上体验还是比较明显。

比如hash得一个memset就是用了60ms, qsort和使用原生的qsort就差距了60ms,取消hash索引还可以降低到150ms

#include 
#include 
#include #define INPUT_MAX	100000
#define TELNUM_NUM	10000000int g_InputNum = 0;
int g_Input[INPUT_MAX];		// 保存不重复的输入。减少hash遍历
int g_iHash[TELNUM_NUM];	// hash所有电话号的重复次数// 相对使用switch case没有明显性能提升
char g_TelChar2UChar[] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1			// 47
, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9				// 48 - 57
, -1, -1									// 58 - 59
, -1, -1, -1, -1, -1						// 64
, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, -1, 7, 7, 8, 8, 8, 9, 9, 9, -1	// 65 - 90
, -1, -1, -1, -1, -1, -1, -1, -1, -1		// 91 - 99
, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
, -1, -1, -1, -1, -1, -1, -1, -1
};inline int TelString2Int(char* pStr)
{int ret = 0;for (int i = 0; i < 7; pStr++){char tempC = g_TelChar2UChar[*pStr];if(tempC != -1){ret = ret * 10 + tempC;i++;}}return ret;
}// 快速排序
// 比使用系统提供的qsort性能提高了60ms左右。
// 可能是系统的qsort都是内存copy和函数调用导致
void qsort(int* pArray, int indexB, int Num)
{// 组织前后int begin = 1;int end = Num - 1;int temp;if (Num < 2){return;}for (begin ; begin < end; begin++){if(pArray[indexB] < pArray[indexB+begin]){for ( ; end > begin; end--){if(pArray[indexB+end] < pArray[indexB]){// 交换temp = pArray[indexB+end];pArray[indexB+end] = pArray[indexB+begin];pArray[indexB+begin] = temp;break;}}}if(begin >= end){break;}}if(pArray[indexB+begin] > pArray[indexB]){begin--;}temp = pArray[indexB+begin];pArray[indexB+begin] = pArray[indexB];pArray[indexB] = temp;if(begin > 1){qsort(pArray, indexB, begin);}if(Num - begin - 1 > 1){qsort(pArray, indexB+begin+1, Num - begin - 1);}
}int main()
{int n = 0;if (scanf("%d", &n) != EOF){g_InputNum = 0;//memset(g_iHash, 0, sizeof(g_iHash));	// 这个函数消耗60msfor (int i = 0; i < n; i++){char strTel[80];			// 电话号码最长7，间隔符+结束符int  iTel;scanf("%s", strTel);iTel = TelString2Int(strTel);g_iHash[iTel]++;if(g_iHash[iTel] == 2){// 刚刚开始重复的电话g_Input[g_InputNum++] = iTel;}}if (g_InputNum < 1){printf("No duplicates.\n");}else{// 只对重复得号码入进行一次快速排序qsort(g_Input, 0, g_InputNum);             //快速排序char outputTemp[2048];int  outputLen = 0;for(int i = 0; i < g_InputNum; i++){int len = sprintf(outputTemp+outputLen, "%03d-%04d %d\n", g_Input[i]/10000, g_Input[i]%10000, g_iHash[g_Input[i]]);outputLen += len;if(outputLen + 10 > 2048){printf(outputTemp);outputLen = 0;}}if (outputLen > 0){printf(outputTemp);outputLen = 0;}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！