如何操作数组以获得最大数量？

Question

假设你有一个正整数数组,操纵它们,以便结果数组的整数串联是可能的最大数.例如:{9,1,95,17,5},结果:9955171

家庭作业警察:这是一个谷歌电话采访问题,并没有签署任何NDAs;).

Answer 1

正如其他人所指出的那样,词典排序和连接是接近的,但并不完全正确.例如,对于数字5,54和56词典排序将产生{5,54,56}(按递增顺序)或{56,54,5}(按递减顺序),但我们真正想要的是{56,5 ,54},因为这会产生尽可能多的数字.

所以我们想要一个两个数字的比较器,以某种方式将最大数字放在第一位.

1. 我们可以通过比较两个数字的个别数字来做到这一点,但是如果另一个数字仍然有剩余数字,我们必须小心谨慎.我们必须要有很多计数器,算术和边缘情况.

2. 一个可行的解决方案(也由@Sarp Centel提到)实现与(1)相同的结果,但代码少得多.这个想法是将两个数字的连接与这些数字的反向连接进行比较.我们必须在(1)中明确处理的所有残余都是隐式处理的.

   例如,比较56和5,我们会做的一个普通字典的比较565来556.从565>开始556,我们会说它56比"更大" 5,应该首先出现.同样,比较54和5意味着我们将测试545< 554,它告诉我们5"比"更大54.

这是一个简单的例子:

// C++0x: compile with g++ -std=c++0x <filename>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main() {
  std::vector<std::string> v = {
    "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"
  };
  std::sort(v.begin(), v.end(),
      [](const std::string &lhs, const std::string &rhs) {
        // reverse the order of comparison to sort in descending order,
        // otherwise we'll get the "big" numbers at the end of the vector
        return rhs+lhs < lhs+rhs;
      });

  for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << ' ';
  }
}

运行时,此代码显示:

9 96 95 56 556 5 55 554 54 3 2 1

Answer 2

看一下例子{5,54,56},订购这些数字的正确方法是在比较字符串A和B时,我们应该考虑A + B与B + A的字典顺序.

例如:

• 比较(5,54)成为("554"与"545")的词典对照
• 比较(5,56)成为("556"和"565")的词典比较
• 比较(54,56)成为("5456"与"5654")的词典比较

如果我们这样排序,结果数组是{56,5,54}.

这是这个想法的Java实现:

public class LexicographicSort implements Comparator<Integer> {

    public int compare(Integer o1, Integer o2) {
        String s1 = o1.toString();
        String s2 = o2.toString();
        return (s2+s1).compareTo(s1+s2);
    }

    public static void main(String[] args) {
        LexicographicSort ls = new LexicographicSort();
        Integer[] nums = {9,1,95,17,5};
        Arrays.sort(nums, ls);
        System.out.println(Arrays.toString(nums));
    }
}

Answer 3

嗯,对于一个你可以试试这个

• 将数字拆分为单个字符
• 按字典顺序按降序对它们进行排序
• 列出了清单

你得到的人数最多