C语言将数组中元素的数排序输出的相关问题解决

问题描述：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32,  321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。
      思路：先将整数数组转为字符串数组，然后字符串数组进行排序，最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义，不是比较a和b，而是比较ab与 ba。如果ab < ba，则a < b；如果ab > ba，则a > b；如果ab = ba，则a = b。比较函数的定义是本解决方案的关键。
      证明：为什么这样排个序就可以了呢？简单证明一下。根据算法，如果a < b，那么a排在b前面，否则b排在a前面。可利用反证法，假设排成的最小数字为xxxxxx，并且至少存在一对字符串满足这个关系：a > b，但是在组成的数字中a排在b前面。根据a和b出现的位置，分三种情况考虑：
      （1）xxxxab，用ba代替ab可以得到xxxxba，这个数字是小于xxxxab，与假设矛盾。因此排成的最小数字中，不存在上述假设的关系。
      （2）abxxxx，用ba代替ab可以得到baxxxx，这个数字是小于abxxxx，与假设矛盾。因此排成的最小数字中，不存在上述假设的关系。
      （3）axxxxb，这一步证明麻烦了一点。可以将中间部分看成一个整体ayb，则有ay < ya，yb < by成立。将ay和by表示成10进制数字形式，则有下述关系式，这里a，y，b的位数分别为n，m，k。
        关系1： ay < ya => a * 10^m + y < y * 10^n + a => a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y
        关系2： yb < by => y * 10^k + b < b * 10^m + y => y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1)
        关系3： a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  => a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b
       这与假设a > b矛盾。因此排成的最小数字中，不存在上述假设的关系。
       综上所述，得出假设不成立，从而得出结论：对于排成的最小数字，不存在满足下述关系的一对字符串：a > b，但是在组成的数字中a出现在b的前面。从而得出算法是正确的。
      参考代码：

//重新定义比较函数对象
struct compare
{
 bool operator() (const string &src1, const string &src2)
 {
  string s1 = src1 + src2;
  string s2 = src2 + src1;
  return s1 < s2; //升序排列，如果改为s1 > s2则为逆序排列
 }
};
//函数功能 ： 把数组排成最小的数
//函数参数 ： pArray为数组,num为数组元素个数
//返回值 ： 无
void ComArrayMin(int *pArray, int num)
{
 int i;
 string *pStrArray = new string[num]; 

 for(i = 0; i < num; i++) //将数字转换为字符串
 {
  stringstream stream;
  stream<<pArray[i];
  stream>>pStrArray[i];
 } 

 sort(pStrArray, pStrArray + num, compare()); //字符串数组排序 

 for(i = 0; i < num; i++) //打印字符串数组
  cout<<pStrArray[i];
 cout<<endl; 

 delete [] pStrArray;
}
赞 (0)

相关推荐

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • c语言合并两个已排序数组的示例(c语言数组排序)

    问题:将两个已排序数组合并成一个排序数组 这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法?),只做简单数组的处理. 简单代码如下: 说明:之所以把merge函数定义成返回数组长度,是因为后续会有重复数据合并功能的merge版本,考虑到接口一致性. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <string.h> int merge(int* ar1, int len1, int

  • c语言实现输入一组数自动从大到小排列的实例代码

    如下所示: #include <stdio.h> main() { int x; printf("请输入要排序数字个数:"); scanf("%d",&x); int i,j,k,a,b,num[x]; printf("输入数据:"); for(i=0;i<x;i++) scanf("%d",&num[i]); for(j=0;j<x;j++) { for(k=j+1;k<x;k+

  • C语言将数组中元素的数排序输出的相关问题解决

    问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个.例如输入数组{32,  321},则输出这两个能排成的最小数字32132.请给出解决问题的算法,并证明该算法.       思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可.这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba.如果ab < ba,则a < b:如果ab > ba,则a > b:如果ab = ba,则a = b.比较

  • C#求数组中元素全排列的方法

    C#求数组中元素全排列的方法

    本文实例讲述了C#求数组中元素全排列的方法.分享给大家供大家参考.具体如下: 1.算法描述 全排列的第一项是该数组的升序排列,最后一项是该数组的降序排列.本文中用到的了一个函数FindNextArray:从升序排列开始,不断使用函数FindNextArray,可以遍历全部排列,最终到达数组中元素的降序排列. FindNextArray函数的实现思路: 设有数组array为原数组的一个排列 1)找出数组的最大值 2)从后向前找:找到第一组array[i]>array[i-1]的数,以i位置为sig

  • python数组中的 k-diff 数对例题解析

    python数组中的 k-diff 数对例题解析

    目录 一.题目描述 二.思路分析 方法一:构建哈希表 方法二:双指针 三.总结 一.题目描述 题目内容: 题目示例: 题目解析: 1 <= nums.length <= 104 -107 <= nums[i] <= 107 0 <= k <= 107 二.思路分析 我们拿到本题,读取题意要求在一组整数数组中,求出差值为k的数对对数k-diff.在思考如何解答该题之前,需要明确如下几点细节: nums数组元素都是整数 索引位置i与位置j,不能相等 k-diff数对关系:n

  • Javascript循环删除数组中元素的几种方法示例

    Javascript循环删除数组中元素的几种方法示例

    本文主要跟大家分享了关于Javascript循环删除数组中元素的几种方法,分享出来供大家参考学习,下面来看看详细的介绍: 发现问题 大家在码代码的过程中,经常会遇到在循环中移除指定元素的需求.按照常规的思路,直接一个for循环,然后在循环里面来个if判断,在判断中删除掉指定元素即可.但是实际情况往往不会像预想的那样顺利运行. 下面以一段Javascript代码为例演示这一过程. (function () { var arr = [1,2,2,3,4,5]; var len = arr.lengt

  • python 统计数组中元素出现次数并进行排序的实例

    如下所示: lis = [12,34,456,12,34,66,223,12,5,66,12,23,66,12,66,5,456,12,66,34,5,34] def test1(): #进行去重 c = [] for i in lis: if i not in c: c.append(i) #进行统计,生成二维列表 b = [] for i in c: num = 0 for j in range(len(lis)): if lis[j] == i: num += 1 a = [] a.app

  • C++实现数组中元素组合出最大值

    C++实现数组中元素组合出最大值

    目录 数组中元素组合出最大值 如题:这可以算是一个算法类 数组或vector求最大值最小值 1.求数组的最大值或最小值 2.求数组最大值最小值对应的下标 数组中元素组合出最大值 如题:这可以算是一个算法类 class Solution { public: string largestNumber(vector<int>& nums) { string res; sort(nums.begin(), nums.end(), [](const int& x, const int&a

  • php usort 使用用户自定义的比较函数对二维数组中的值进行排序

    今天发现一个很好用二维数组排序的php方法,usort,推荐给大家,以后二维数组里面,要按照一个字段的值排序用这个方法简单高效,例如下面的数组: [guess_subject] => Array ( [0] => Array ( [subject_id] => 4587 [game_id] => 9228 [parent_category_id] => 78 [subject_title] => 全场比赛两队总得分之和是 [subject_date_time] =>

  • js 根据对象数组中的属性进行排序实现代码

    这篇文章主要介绍了js 根据对象数组中的属性进行排序实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 var arr = [ {name:'a',age:9}, {name:'b',age:12}, {name:'c',age:8} ]; arr.sort((a,b)=>{ return a.age - b.age }); function compare(property){ return function(a,b){ var

  • java中 Set与Map排序输出到Writer详解及实例

    java中 Set与Map排序输出到Writer详解及实例

     java中 Set与Map排序输出到Writer详解及实例 一般来说java.util.Set,java.util.Map输出的内容的顺序并不是按key的顺序排列的,但是java.util.TreeMap,java.util.TreeSet的实现却可以让Map/Set中元素内容以key的顺序排序,所以利用这个特性,可以将Map/Set转为TreeMap,TreeSet然后实现排序输出. 以下是实现的代码片段: /** * 对{@link Map}中元素以key排序后,每行以{key}={val

  • PHP中unset,array_splice删除数组中元素的区别

    如果要在某个数组中删除一个元素,可以直接用的unset,但是数组的索引不会重排: <?php $arr = array('a','b','c','d'); unset($arr[1]); print_r($arr); ?> 结果是: Array ( [0] => a [2] => c [3] => d )   那么怎么才能做到缺少的元素会被填补并且数组会被重新索引呢?答案是array_splice(): <?php $arr = array('a','b','c','d

随机推荐