Как я могу манипулировать массивом, чтобы сделать наибольшее число?

Question

Скажем, у вас есть массив положительных целых чисел, манипулируйте ими так, чтобы конкатенация целых чисел из результирующего массива была наибольшим возможным числом.Пример: {9,1,95,17,5}, результат: 9955171

Полиция по домашним заданиям: это был вопрос по телефону из Google, и NDA не были подписаны;).

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 <<code>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

Ну, для одного вы можете попробовать это

• разделить числа на отдельные символы
• отсортировать их лексикографически в порядке убывания
• составить список

Вы получили наибольшее число

Answer 4

Вот реализация в c ++

#include <stdio.h>
#include <sstream>

using namespace std;

/**
    a = 123
    b = 15
    v1 = 12315
    v2 = 15123
    return (v2 - v1) to make the function sort in descending order
*/
int compare_concatenated_ints(const void *arg1, const void *arg2)
{
    int v1 = *(int*) arg1;
    int v2 = *(int*) arg2;

    stringstream s1, s2;
    s1 << v1 << v2;
    s2 << v2 << v1;

    s1 >> v1;
    s2 >> v2;

    return (v2 - v1);
}

void print_array(int arr[], int count)
{
    for (int i = 0; i < count; ++i){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = {4, 0, 94, 9, 14, 0, 1};    
    int count = sizeof(arr)/sizeof(arr[0]);

    printf("BEFORE\n");
    print_array(arr, count);

    std::qsort(arr, count, sizeof(int), compare_concatenated_ints);

    printf("AFTER\n");
    print_array(arr, count);
}

Answer 5

Не уверен, если кто-то ищет решение JavaScript, но если вы, вот код

function LexicographicSort(input) {
    return Number(
        input
            .sort(function(a, b) {
// lexicographic sort
               return Number("" + b + a) - Number("" + a + b);
            })
            .join("")
        );
}

Answer 6

Я думаю, это уже решено.Вот несколько строк кода в Python, использующих логику, которая уже обсуждалась в нескольких ответах:

>>li = [9,1,95,17,5]
>>li.sort(cmp=lambda a,b: cmp(int(str(a)+str(b)), int(str(b) + str(a))), reverse=True)

>>output = ""
>>for i in li:
output += str(i)

>>print  output

Answer 7

Идея @Nate Kohl очень хорошая.Я только что реализовал версию Java с помощью быстрой сортировки.Вот оно:

import java.util.Random;

public class Sort_MaxConcatenation {
    private Random r = new Random();

    public void quicksort_maxConcatenation(int[] a, int begin, int end) {
        if (begin < end) {
            int q = partition(a, begin, end);
            quicksort_maxConcatenation(a, begin, q);
            quicksort_maxConcatenation(a, q + 1, end);
        }
    }

    private int partition(int[] a, int begin, int end) {
        int p = begin + r.nextInt(end - begin + 1);
        int t1 = a[p];
        a[p] = a[end];
        a[end] = t1;

        int pivot = t1;
        int q = begin;
        for (int i = begin; i < end; i++) {
            if (compare_maxConcatenation(a[i], pivot) > 0) {
                int t2 = a[q];
                a[q] = a[i];
                a[i] = t2;
                q++;
            }
        }
        int t3 = a[q];
        a[q] = a[end];
        a[end] = t3;

        return q;
    }

    private int compare_maxConcatenation(int i, int j) {
        int ij = Integer.valueOf(String.valueOf(i).concat(String.valueOf(j)));
        int ji = Integer.valueOf(String.valueOf(j).concat(String.valueOf(i)));
        if (ij > ji)
            return 1;
        else if (ij == ji)
            return 0;
        return -1;
    }

    public static void main(String[] args) {

        int[] a = new int[]{56, 5, 4, 94, 9, 14, 1};
        Sort_MaxConcatenation smc = new Sort_MaxConcatenation();
        smc.quicksort_maxConcatenation(a, 0, a.length-1);
        for(int i = 0;i < a.length;i++) {
            System.out.print(a[i]);
        }
    }
}

Answer 8

Вот решение Python 3, где a - массив, а n - общее количество элементов

def check(p,q):
    p=str(p)
    q=str(q)
    d=max(p+q,q+p)
    if d==p+q:
        return int(p),int(q)
    else:
        return int(q),int(p)
def find(a,n):
    for i in range(n):
        for j in range(n-1):
            c,d=check(a[j],a[j+1])
            a[j]=c
            a[j+1]=d
    print(*a,sep="")

Answer 9

Вот простая реализация в Java без использования компаратора

import java.util.List;

import java.util.ArrayList;

import java.util. *;

import java.lang.Math;

открытый класс LargestNumber {

public static void main(String args[]){
    ArrayList<Integer> al = new ArrayList<Integer>(); 
    al.add(872);
    al.add(625);
    al.add(92);
    al.add(8);
    al.add(71);

    Find find = new Find();
    find.duplicate(al);
    }

}

класс Найти {

public void duplicate(ArrayList<Integer> al){
    String numL ="";
    int size = al.size();
    Collections.sort(al,Collections.reverseOrder());
    ArrayList<Integer> arrL = new ArrayList<Integer>();
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size - 1; j++){
            if((compare(al.get(j), al.get(j+1))) == 1){
                Collections.swap(al,j,j+1);
            }
        }
    }

    for(int i = 0; i < size; i++){
        numL = numL + al.get(i);
    }
    System.out.println(numL);

}

public static int compare(int x, int y){

    String xStr = String.valueOf(x);
    String yStr = String.valueOf(y);

    int a = Integer.parseInt(xStr+yStr);
    int b = Integer.parseInt(yStr+xStr);

    return (a>b)? 0:1;
}

}

выход 92887271625

Answer 10

Хорошо, как насчет этого алгоритма, который использует функцию сравнения, чтобы проверить предыдущее число и число в следующем индексе. Для простоты я использовал строки вместо целых чисел. Хотя алгоритм хорошо объясняет, что он делает .

  #include<string>
  #include<iostream>
  #include<algorithm>
  using  namespace std;

  int main(){
  bool arranged=false;
  string arr[]={"98","12","56","9"};
  for(int i=0;i<4;i++)
    cout<<arr[i]<<" ";
    cout<<endl;

while( arranged==false )
{ 
string previous = arr[0];
  arranged = true;
  for(int i = 1; i < 4;i++)
  { 
    string  XY = (previous + arr[i] ); 
    string  YX = (arr[i] + previous);        
      if ( YX.compare(XY) > 0 ) {
     swap(arr[i],arr[i-1]);
     arranged = false;
    }
   previous = arr[i];  
    }
 }

   for(int i=0;i<4;i++)
   cout<<arr[i];

   return 0;
 }