金沙国际app-金沙国际手机app下载

金沙国际app包括教育和科研机构建设、学科共建等,欢迎来到金沙国际手机app下载这里有多种线上娱乐游戏,金沙国际app获颁“创意中国榜”中国文化创意产业领军企业,是一家专业从事网络休闲平台游戏开发、运营的服务性企业。

当前位置:金沙国际app > 网络世界 > 贪心算法——最大数问题:贪心法、二叉排序与

贪心算法——最大数问题:贪心法、二叉排序与

文章作者:网络世界 上传时间:2019-11-10

贪心算法——最大数问题:贪心法、二叉排序与指针,贪心二叉

问题:

  给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。

样例:

  给出 [1, 20, 23, 4, 8],返回组合最大的整数应为8423201

挑战:

  时间复杂度:O(nlogn)

问题来源:

  http://www.lintcode.com/zh-cn/problem/largest-number/

 

思路:

  两种思路:

  一:

    1、将vector内所有元素的所有位都分别按元素顺序保存在二维数组中;//O(Cn)

    2、比较vecotr内所有元素的首位的大小,以样例为例,即比较1,2,2,4,8的大小,并排序记录其位置,排序可采用二叉排序;//时间复杂度为O(nlogn)

    3、基于上一步,进行第二位排序,没有第二位的则不参与排序,记录排序后的位置;//时间复杂度为O(nlogn)

    4、重复以上过程,直至不存在元素没有位参与排序;//总时间复杂度为O(nlogn)

    5、基于已经记录的位置进行输出。

  二:

    1、找到vector所有元素的最大值,确认是否与int极限处于同一数量级,不处于则进行步骤2,处于则进行步骤3;//O(n)

    2、如果最大值与int极限不处于同一数量级,则将其余所有数都提升到最大值所在数量级,然后直接二叉排序,记录其位置,并根据位置进行输出;//O(nlogn)

    3、如果最大值与int极限处于同一数量级,则统计vector所有元素中该数量级的元素,并二叉排序,记录其位置;//O(nlogn)

    4、将上一步骤排序后的元素除10,并顺序递减;//O(n)

    5、将vector中其余元素提升到上一步骤的数量级,将所有元素排序,并记录其位置,并根据位置进行输出;//O(nlogn)

 

  其实上面两种思路归结起来都可以算是同一种思路,都是将所有元素处于同一量级之后进行排序,但不同的点在于,一个是降量级操作,一个是升量级操作。

  降量级操作因为需要元素的每一位都需要排序,所以相对的常数C会大一些。并且因为需要记录额外的元素位信息,空间复杂度也会相应大一些。

  所以本文采用了升量级操作。升量级操作最值得注意的一点就是不可超过int极限,所以当存在元素与int极限处于同一量级时,首先需要对这些元素进行将量级操作,再将其余元素升量级。

 

Code:

  1 class Solution {
  2 public:
  3     /*
  4      * @param nums: A list of non negative integers
  5      * @return: A string
  6      */
  7     string largestNumber(vector<int> &nums) {
  8         // write your code here
  9         vector<int> order_nums = nums;
 10         vector<int> sort_nums = nums;
 11         vector<int> sitea = nums;
 12         vector<int> siteb = nums;
 13         vector<int> overnum, oversite;
 14         int MaxN = nums.size();
 15         int IntMax = 1 << 31;//取得int极限
 16         int NumMax = 0;
 17         int Nlevel = 0;
 18         int gain = 1;
 19         int Ilevel = 0;
 20         int Tmp = -1;
 21         string out = "";
 22         if (MaxN <= 1) {//简单的异常与情况处理
 23             if (MaxN){
 24                 return to_string(nums[0]);
 25             }
 26             return "";
 27         }
 28         for (int i = 0; i < MaxN; i++) {//寻找最大值,时间复杂度O(n)
 29             sitea[i] = 0;
 30             if (NumMax < nums[i]) {
 31                 NumMax = nums[i];
 32             }
 33         }// O(n)
 34         Tmp = NumMax / 10;//记录最大值的降量级值
 35         if (!NumMax) {//简单情况处理
 36             return "0";
 37         }
 38         while (NumMax) {//获取最大值量级
 39             Nlevel++;
 40             NumMax /= 10;
 41         }// O(c)
 42         while(IntMax) {//获取int极限量级
 43             Ilevel++;
 44             IntMax /= 10;
 45         }
 46         if (Nlevel == Ilevel) {//最大值量级与int极限量级是否一致
 47             gain *= pow(10, Nlevel - 2);//升量级后的最小值
 48             for (int i = 0; i < MaxN; i++) {//获得所有与最大值量级处于同一量级的数
 49                 if(order_nums[i] >= gain) {
 50                     overnum.insert(overnum.end(), order_nums[i]);
 51                     oversite.insert(oversite.end(), i);
 52                 }
 53             }
 54             vector<int> oversort = overnum;
 55             vector<int> sortsite = oversite;
 56             vector<int> storesite = oversite;
 57             twosort(oversort, overnum, sortsite, oversite, 0, overnum.size() - 1, (overnum.size() - 1) / 2);//将所有与最大量级处于同一量级的数排序并记录其位置
 58             for (int i = 0; i < oversort.size(); i++) {//将所有与最大量级处于同一量级的数降量级操作
 59                 nums[storesite[i]] = oversort[i];
 60                 order_nums[storesite[i]] = sort_nums[storesite[i]] = Tmp--;
 61             }
 62         }
 63         else {
 64             gain *= pow(10, Nlevel - 1);//升量级后的最小值
 65         }
 66         for (int i = 0; i < MaxN; i++) {//根据gain值进行升量级操作
 67             siteb[i] = i;
 68             order_nums[i] = gainnum(order_nums[i], gain, order_nums[i]);
 69             //cout << order_nums[i] << " " << gain << endl;
 70         }// O(cn)
 71         twosort(order_nums, sort_nums, sitea, siteb, 0, MaxN - 1, (MaxN - 1) / 2);//将所有数进行排序并记录其位置
 72         for (int i = 0 ;i < MaxN; i++) {//根据位置,将所有值输出
 73             out += to_string(nums[sitea[i]]);
 74         }
 75         return out;
 76     }
 77 
 78     int gainnum(int num, const int gain,const int ori) {//升量级函数,根据传入的gain值判断是否num是否已经达到对应量级,并判断num为0的情况
 79         if (num >= gain || !num) {
 80             //cout << num << endl;
 81             return num;
 82         }
 83         //cout << num << endl;
 84         return gainnum(num * 10 + ori, gain, ori);//确保升量级操作后的num数为原初num数的1...1倍
 85     }
 86 
 87     int twosort(vector<int> &nums, vector<int> &sort, vector<int> &sitea, vector<int> &siteb, const int start, const int end, int mid) {//二叉排序算法,并同时记录位置
 88         if (start >= end) {//当数组起始位置大于等于末尾位置时,可认为已排序
 89             return 0;
 90         }
 91         int fr = start, bc = end, MidNum = nums[mid], tmp =start;
 92         for (int i = start; i <= end; i++) {
 93             if (nums[i] > MidNum) {//大则将值置于数组前段
 94                 sort[fr] = nums[i];
 95                 sitea[fr] = siteb[i];
 96                 fr++;
 97             }
 98             else if (nums[i] < MidNum) {//小则将值置于数组后段
 99                 sort[bc] = nums[i];
100                 sitea[bc] = siteb[i];
101                 bc--;
102             }
103             else {//等于则略过
104                 continue;
105             }
106         }//O(n)
107         tmp = fr;
108         for(int i = start; i <= end; i++) {//将相等情况平行放入前段与后段的中间位置
109             if (nums[i] == MidNum) {
110                 sort[tmp] = nums[i];
111                 sitea[tmp] = siteb[i];
112                 tmp++;
113             }
114         }//O(n)
115         if ((bc == end && tmp <= bc)) {//当所有元素都大于该数组最后一个值,且前段+相等情况的大小皆处于数组范围内时,可认为已经排序完成
116             nums = sort;
117             siteb = sitea;
118             return 0;
119         }
120         nums = sort;
121         siteb = sitea;//将数组和位置赋予另一数组和位置,以便下一轮排序
122         twosort(nums, sort, sitea, siteb, start, fr - 1, (start + fr - 1) / 2);//前段排序
123         twosort(nums, sort, sitea, siteb, tmp, end, (tmp + end) / 2);//后端排序
124         return 0;
125     }//O(nlogn)
126 };

 

贪心法:

  本题是贪心法的一个很简单的题目应用,如采用第一种方法,则可以明显看到每一步都是在寻找当前位的最大值,直到到达峰顶(也就是不存在下一位的情况)。第二种方法虽然最多只有两步排序,但也采用了同样的思路:找到同一量级的最大值,然后排序输出。

 

二叉排序&指针:

  二叉排序的思路主要就是将大于中间位置值的数往数组前/后段上排列,小于则往另一段上排列,存在多个与中间位置值相同的值时,则建议平行插入前后段已经确认的中间位置,不改变其顺序。

  重复调用本身,即可完成整个数组的排列。

  不过需要注意的时,函数传递参数时是传递该参数的一份拷贝,不是该参数本身,所以twosort要将排序好的值及其对应位置传递出来时,需要取其地址传入。

  即:int twosort(vector<int> &nums, vector<int> &sort, vector<int> &sitea, vector<int> &siteb, const int start, const int end, int mid)

  本文采用vector向量,不采用数组则是因为数组传递进去的是数组首地址,而要赋值的话,则不能直接进行siteb=sitea这样的赋值操作,这样只会将siteb的指针指向sitea的指针指向的位置,即&sitea[0]。

  所以若要采用数组,又想对数组进行赋值,则需要使用for循环进行赋值,虽然时间复杂度在n的情况下,总体不变,但是代码就会冗余一些。

  而采用vector向量则可以避免该问题,虽然twosort传入的也是vector向量的地址,但进行操作时,并不是针对地址进行操作,而只是值发生改变,并且vector向量可以进行(vector<int>) a = (vector<int>) b这样的操作,在代码上就会简洁清晰。

 

题目虽然不难,但是对贪心法和二叉排序的认知就因此上了一个步骤,不再只是看了看书和看了看代码的程度。

http://www.bkjia.com/cjjc/1226596.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1226596.htmlTechArticle贪心算法——最大数问题:贪心法、二叉排序与指针,贪心二叉 问题: 给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整...

本文由金沙国际app发布于网络世界,转载请注明出处:贪心算法——最大数问题:贪心法、二叉排序与

关键词: