Скажите, что у вас есть массив положительных целых чисел, манипулируйте ими, так что объединение целых чисел результирующего массива является наибольшим возможным числом. Пример: {9,1,95,17,5}, результат: 9955171
Домашние полицейские: это был вопрос интервью с телефоном Google, и никаких NDA не было подписано;).
Как отмечали другие, лексикографическая сортировка и конкатенация близки, но не совсем корректны. Например, для чисел 5, 54 и 56 лексикографическая сортировка будет производить {5, 54, 56} (в порядке возрастания) или {56, 54, 5} (в порядке убывания), но мы действительно хотим {56, 5, 54}, так как это дает наибольшее возможное число.
Итак, нам нужен компаратор для двух чисел, который сначала ставит самые большие цифры.
Решение cuter (также упоминаемое @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
Рассматривая пример {5,54,56}, правильный способ упорядочить эти числа - при сравнении строк A и B, мы должны рассмотреть лексикографическое упорядочение A + B с B + A.
Например:
Если мы отсортируем их таким образом, результирующий массив будет {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));
}
}
Хорошо, для одного вы можете попробовать это
У вас наибольшее число
#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);
}
Идея @Nate Kohl очень хорошая. Я только что реализовал версию Java, использующую quicksort. Вот он:
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]);
}
}
}
Я думаю, это уже было решено. Вот несколько строк кода в 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
Я бы использовал следующую функцию для их сортировки
class Kakira {
static int preferred(int a, int b) {
if(a == b) return a; // doesn't matter which
String sa = a+"";
String sb = b+"";
for(int i = 0; i < sa.length() && i < sb.length(); i++) {
char ca = sa.charAt(i);
char cb = sb.charAt(i);
if(ca < cb) return b;
if(ca > cb) return a;
}
// we reached here - the larger one must start with the smaller one
// so, remove the small one from the start of the small one, and
// that will tell us which is most appropriate.
if(a < b) {
String choppedB = sb.substring(sa.length());
if(preferred(Integer.parseInt(choppedB),a) == a)
return a;
else
return b;
}
else {
String choppedA = sa.substring(sb.length());
if(preferred(Integer.parseInt(choppedA),b) == b)
return b;
else
return a;
}
}
// using a very simple sort because I'm being lazy right now
public static void sort(int[] data) {
while(!isSorted(data)) {
for(int i = 0; i < data.length - 1; i++) {
int a = data[i];
int b = data[i+1];
int p = preferred(a,b);
if(p == b) {
data[i] = b;
data[i+1] = a;
}
}
}
}
public static boolean isSorted(int[] data) {
for(int i = 0; i < data.length - 1; i++) {
int a = data[i];
int b = data[i+1];
int p = preferred(a,b);
if(p != a) return false;
}
return true;
}
public static void main(String[] args) {
int[] data = new int[]{9,1,95,17,5};
sort(data);
for(int i : data) System.out.print(i);
System.out.println("");
}
}
Для людей: Во-первых: я собираюсь сортировать их, используя специальную функцию сравнения. Это поставит их в самый желаемый порядок, поэтому мы можем просто распечатать их.
Я не беспокоюсь о алгоритме сортировки, потому что, как только вы проведете сравнение, вы можете использовать любую сортировку, которую хотите. Сравнение - важная часть.
Итак, пройдите через процесс принятия решений.
Во-первых, если оба числа равны, никто не заботится о том, какой он есть. Поэтому мы просто возвращаем его.
Затем мы получаем строковое представление чисел, чтобы мы могли начать сравнивать цифры. Мы спускаем цифры, пока не закончим цифры на одной из строк. Как только они перестают быть равными, мы хотим, чтобы один с большим значением, потому что мы хотим ранние цифры (я думаю, что это понятно).
Если мы дойдем до конца одного из чисел, и у нас пока нет победителя, мы знаем, что дольше нужно начинать с короткого. Они НЕ МОГУТ быть одинаковой длины, потому что, если первые цифры равны, и они равны по длине, то сами числа равны, и они были бы пойманы ранее в этом процессе. Итак, вопрос в том, что первый идет? Ну, рассмотрим последствия:
12345 first: 12345123
123 first: 12312345
Очевидно, мы хотим первого. Но как это знать? Мы берем 123 от длинного. Итак, у нас есть 45 и 123.
Теперь, запустите их через алгоритм снова, определите, кто был победителем, и в зависимости от того, что выиграл второй раунд, также выигрывает первый раунд. Если бы он пошел глубже, скажем (12312312 и 123), то он будет продолжать двигаться вниз.
Имеют смысл?
Edit:
Создайте массив, содержащий все возможные конкаты исходного массива
Вы получаете:
{91 , 19} При объединении 1 и 9
{995 , 959}, когда 9 и 95
{917 , 179}, когда 9 и 17
из всех этих кортежей получают большее число. и удалите из массива числа, которые использовались для создания этой строки concat, и из кортежей удаляют все конкаты, которые используют эти числа, чтобы избежать очевидной ошибки. Найдите следующее большое число в кортежах и т.д. И т.д....
У меня есть общая идея относительно того, как я буду заниматься этим, но я не уверен, как заставить его работать для любых других чисел, превышающих 2 цифры, возможно, это поможет вам.
{9,1,95,17,5}
ok разбивает массив на два массива, один из которых содержит цифры с одной цифрой, а другой - две цифры.
сортировать их
вы получаете {95 , 17} и {9,5,1}
сравните, если A1 [0] + A2 [0] > A2 [0] + A1 [0] лексикографически,
например 959 > 995 (+ в этом случае не является математическим дополнением, а строкой concat)
и получить больше этих двух
то вы останетесь с 995 и {17} и {5,1}
снова 175 > 517?
вы получите 995-517, и вы остаетесь с {1}
Надеюсь, что поможет
Интересный вопрос. Я предполагаю, что сначала вы можете начать с самого простого подхода, который будет использовать грубую силу для создания всех возможных чисел с использованием рекурсии (в зависимости от проблемы и языка, которые могут быть изменены на итерации) и отслеживать, какой из них самый большой. Например, {1, 83, 91} даст вам {18391, 19183, 83191, 83911, 91183, 91831}, из которых вы можете определить 91831 как наибольшее число.
Используя решение, которое сортирует исходные числа и объединяет числа в порядке, имеет ошибку в том, что если у вас есть что-то вроде {9, 82, 99}, отсортированный массив будет {99, 82, 9}. Однако это приведет к 99829, когда наибольшее число будет фактически 99982.
Поскольку решение грубой силы работает, но может быть не оптимальным с точки зрения производительности, может быть полезно проверить способы оптимизации решения (конечно, после профилирования исходного решения). Например, вы можете начать с простой схемы упорядочения путем умножения отдельных цифр числа на место, которое они будут занимать.
{ 9, 98, 95 }
Приведенный выше набор приведет к пятизначному числу. Мы применим простую формулу, которая умножает индивидуальную цифру на свое место (1 на 1 место, 2 на 10 место и т.д.) И суммирует их так:
9 -> 9 * 5
98 -> 9 * 5 + 8 * 4
95 -> 9 * 5 + 5 * 4
что приводит к
9 -> 45
98 -> 77
95 -> 65
Теперь, как люди, мы знаем, что 9 должны быть первыми, а не 98 или 95. Один из способов исправить это: если бы первые цифры кандидатов были идентичны (то есть, пользу 9 или 98/95/др.). Обобщая бит, вы можете выбрать кандидата с меньшим количеством цифр каждый раз, если цифры слева больше или эквивалентны (если количество цифр равно, используйте приведенную выше формулу). Если у нас есть {9871, 986}, 9871 будет иметь более высокое значение, но мы будем смотреть на 986 и видеть, что у него меньше цифр.
9 8 7 1
| | | |
9 8 6
8 совпадений, продолжение, 7 больше, поэтому игнорируйте 986 (9871986 против меньшего 9869871). Если набор был {9861, 987} вместо:
9 8 6 1
| | | |
9 8 7
8 совпадений, продолжение, 7 больше, поэтому выберите 987 (9879861 против меньшего 9861987).
Итак, тестируем это, используя следующий набор:
{ 7, 61, 811, 99 }
Результат будет 8-значным числом. Применение формулы размещения дает:
7 -> 7 * 8 = 56
61 -> 6 * 8 + 1 * 7
811 -> 8 * 8 + 1 * 7 + 1 * 6 = 77
99 -> 9 * 8 + 9 + 7 = 135
Итак, 99 выглядит так, как будто это будет первым, но теперь примените вторую часть алгоритма, выбрав числа с меньшим количеством цифр:
7
7 не совпадает с 9, конечно, поэтому мы остаемся с 99 как первое число.
9 9 _ _ _ _ _
Следующая итерация:
7 -> 7 * 6 = 42
61 -> 6 * 6 + 1 * 5 = 41
811 -> 8 * 6 + 1 * 5 + 1 * 4 = 57
811 имеет самое высокое значение, и оба 61 и 7 не имеют одинаковых цифр слева направо, поэтому мы вставляем 811.
9 9 8 1 1 _ _ _
Следующая итерация:
7 -> 7 * 3 = 21
61 -> 6 * 3 + 1 * 2 = 20
7 имеет более высокое значение и ничего меньше, чем цифры - insert:
9 9 8 1 1 7 _ _
Следующая итерация:
Осталось только одно число (61), поэтому мы вставим его
9 9 8 1 1 7 6 1 -> 99811761
и получите самое большое число! Обратите внимание, что если бы 61 был чем-то вроде 81, он правильно попал бы в 811 пятно → 99818117 вместо неправильного 99811817.
Это мое решение, хотя оно может быть неэффективным. Код находится в python1.3
#! /usr/bin/env python
def sort(arr):
temparr = []
for num in arr:
l = len(str(num)) - 1
n = num / pow(10, 1)
temparr.append((n, num))
temparr.sort()
temparr.reverse()
return [t[1] for t in temparr]
def buildNum(arr):
finalNum = None
for num in arr:
snum = str(num)
if not finalNum:
finalNum = snum
else:
n1 = finalNum + snum
n2 = snum + finalNum
if n1 >= n2:
finalNum = n1
else:
finalNum = n2
return finalNum
def main():
arr = [9,1,95,17,5]
arr = sort(arr)
print buildNum(arr)
main()
Моя стратегия - использовать любой алгоритм сортировки с пользовательской функцией сравнения.
Прежде чем погрузиться в код, рассмотрим следующие вещи:
Если число цифр равно, то сравнение выполняется прямо. Но если количество цифр неравномерно, то мы извлекаем самую левую цифру целого числа с большим количеством цифр (а затем сравниваем рекурсивно).
Код лучше объясняет. Итак, вот мой рабочий код:
int numDigits(int number)
{
int digits = 0;
if (number < 0) digits = 1; // remove this line if '-' counts as a digit
while (number) {
number /= 10;
digits++;
}
return digits;
}
int comparator ( const void * elem1, const void * elem2 )
{
int x = *(int *)elem1;
int y = *(int *)elem2;
if(x==y) return 0;
int xLen = numDigits(x);
int yLen = numDigits(y);
if(xLen==yLen)
{
return x>y ? -1 : +1;
}
else
{
int xTens = pow((double)10,(double)xLen-1);
int yTens = pow((double)10,(double)yLen-1);
int xLeftmostDigit = (xTens != 0) ? x/xTens : 0;
int yLeftmostDigit = (yTens != 0) ? y/yTens : 0;
if( xLeftmostDigit == yLeftmostDigit )
{
if(xLen<yLen)
{
int yStrippedOutOfLeftmostDigit = y - yLeftmostDigit*yTens;
return comparator(&x, &yStrippedOutOfLeftmostDigit);
}
else
{
int xStrippedOutOfLeftmostDigit = x - xLeftmostDigit*xTens;
return comparator(&xStrippedOutOfLeftmostDigit, &y);
}
}
else
{
return xLeftmostDigit > yLeftmostDigit ? -1 : +1;
}
}
return false;
}
Я написал эту функцию специально для использования с stl qsort.
Это мой тестовый код:
int main(int argv,char **argc) {
//Ex: {9,1,95,17,5}, result: 9955171
int arr[] = {9,1,95,17,5};
int arrLen = 5;
for(int i=0; i<arrLen; i++)
{
cout << arr[i] << "_" ;
}
cout << endl;
qsort(arr, 5, sizeof(int), comparator);
for(int i=0; i<arrLen; i++)
{
cout << arr[i] << "_" ;
}
cout << endl;
}
В С#
static void Concat(params int[] array)
{
List<int> values = new List<int>(array);
values.Sort((a, b) =>
{
StringBuilder asb = new StringBuilder(a.ToString());
StringBuilder bsb = new StringBuilder(b.ToString());
int lengthDiff = asb.Length - bsb.Length;
if (lengthDiff == 0)
return -a.CompareTo(b);
else if (lengthDiff > 0)
bsb.Append(bsb[bsb.Length - 1], lengthDiff);
else
asb.Append(asb[asb.Length - 1], -lengthDiff);
return -asb.ToString().CompareTo(bsb.ToString());
});
Если вы знакомы со знаменательными битами, вы можете видеть, что это делает именно это только в обратном порядке. Он расширяет более короткую длину последней цифры до той же длины, и они просто возвращают сравнение строк.
Хорошо, как насчет этого алгоритма, который использует функцию сравнения для проверки предыдущего номера и числа в следующем индексе. Для простоты я использовал строки вместо целых чисел. Хотя алгоритм хорошо объясняет, что он делает.
#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;
}
Вот простая реализация в java без использования компаратора
импортировать java.util.List;
import java.util.ArrayList;
import java.util. *;
импортировать java.lang.Math;
public class 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);
}
}
class Найти {
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