The C language solves the problem of sorting the output of the number of elements in an array

  • 2020-05-09 19:00:36
  • OfStack

  problem description: input an array of positive integers, concatenate them into a number, and output the smallest number that can be emitted. For example, the input array {32,   321} outputs the two smallest Numbers that can be aligned, 32132. Please give the algorithm to solve the problem and prove the algorithm.
          idea: first, convert an array of integers into a string array, then sort the string array, and then output the string array in turn. Note here that the string comparison function needs to be redefined to compare a and b, but ab and ba. If ab < ba a < b; If ab > ba a > b; If ab = ba, a = b. The definition of the comparison function is the key to this solution.
          proof: why does this order work? Simple proof 1. According to the algorithm, if a < b, then a comes before b, otherwise b comes before a. By contradiction, assume that the minimum number in the array is xxxxxx, and that at least one pair of strings satisfies this relationship: a > b, but a comes before b in the constituent Numbers. According to the location of a and b, there are three cases to consider:
          (1) xxxxab, ba instead of ab you get xxxxba, which is less than xxxxab, contradicting the hypothesis. Therefore, there is no such relationship in the smallest number of permutations.
        (2) abxxxx, substitute ba for ab to get baxxxx, which is less than abxxxx, contradicting the hypothesis. Therefore, there is no such relationship in the smallest number of permutations.
          (3) axxxxb, this step proves a point of trouble. You can view the middle part as a whole, ayb, then ay < ya, yb < by was established. If ay and by are expressed in the form of base 10 digits, the following relation can be obtained. Here, the digits of a, y and b are n, m and k, respectively.
              relationship 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
              relationship 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)
            relation 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
            this is the same thing as a > b contradiction. Therefore, there is no such relationship in the smallest number of permutations.
To sum up, it is concluded that the hypothesis is not valid and that there is no 1 pair of strings that satisfy the following relation for the minimum number of the array: a           > b, but a appears before b in the constituent Numbers. So the algorithm is correct.
          reference code:


// Redefine the comparison function object  
struct compare 
{ 
 bool operator() (const string &src1, const string &src2) 
 { 
  string s1 = src1 + src2; 
  string s2 = src2 + src1; 
  return s1 < s2; // In ascending order, if changed s1 > s2 Is in reverse order  
 } 
}; 
// The functionality   :   Arrange the array into the smallest number  
// Function parameters   :  pArray As an array ,num Is the number of elements in the array  
// The return value   :   There is no  
void ComArrayMin(int *pArray, int num) 
{ 
 int i; 
 string *pStrArray = new string[num]; 
 
 for(i = 0; i < num; i++) // Converts a number to a string  
 {  
  stringstream stream; 
  stream<<pArray[i]; 
  stream>>pStrArray[i]; 
 } 
 
 sort(pStrArray, pStrArray + num, compare()); // String array sort  
 
 for(i = 0; i < num; i++) // Print string array  
  cout<<pStrArray[i]; 
 cout<<endl; 
 
 delete [] pStrArray; 
} 


Related articles: