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

Question

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

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

Answer 1

В C #

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());
        });

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

Answer 2

Моя стратегия состоит в том, чтобы использовать любой алгоритм сортировки с пользовательской функцией сравнения.

Прежде чем мы углубимся в код, рассмотрим несколько вещей:

Если количество цифр равнотогда сравнение прямое.Но если количество цифр неравно, то мы извлекаем крайнюю левую цифру целого числа с большим количеством цифр (а затем сравниваем рекурсивно).

Код объясняет лучше всего.Итак, вот мой рабочий код:

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;
}

Я написал вышеупомянутую функцию специально для использования с qsort stl.

Это мой тестовый код:

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;
}

Answer 3

Это мое решение, хотя оно может быть неэффективным. Код в 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()

Answer 4

Интересный вопрос. Я полагаю, что вы могли бы начать с самого простого подхода, который бы использовал грубую силу для создания всех возможных чисел с использованием рекурсии (в зависимости от проблемы и языка, это может быть изменено на итерацию) и отслеживал, какой из них самый большой. Например, {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 имеет более высокое значение и ничто не имеет меньше цифр - вставьте:

9 9 8 1 1 7 _ _

Следующая итерация:

Осталось только одно число (61), поэтому мы вставим его

9 9 8 1 1 7 6 1 -> 99811761

и получите наибольшее число! Обратите внимание, что если бы 61 был чем-то вроде 81, он бы правильно оказался на месте 811 -> 99818117 вместо неправильного 99811817.

Answer 5

Редактировать:

Создать массив, который содержит все возможные конкататы исходного массива

Вы получите:

{91 , 19} При объединении 1 и 9

{995 , 959}, когда 9 и 95

{917 , 179}, когда 9 и 17

из всех этих кортежей получают большее число.и удалите из массива числа, которые использовались для создания этой строки конкатов, и из кортежей удалите все конкататы, которые используют эти числа, чтобы избежать очевидной ошибки.Найти следующий большой номер в кортежах и т.д ... и т.д ...

---

У меня есть общее представление о том, как мне поступить, но я не уверен, как заставить это работать налюбые другие числа больше 2 цифр, может быть, это вам поможет.

{9,1,95,17,5}

ok разбейте массив на два массива, один из которых содержит однозначные числа, а другой - две цифры.

сортировать их

вы получите {95 , 17} и {9,5,1}

сравнить, если A1 [0] + A2 [0]> A2 [0] + A1 [0]лексикографически, например 959> 995 ???(+ в данном случае не математическое сложение, а конкат строки)

и получите большее из этих двух

, тогда у вас снова останется 995, {17} и {5,1},175> 517?

вы получаете 995-517, и у вас остается {1}

Надежда, которая помогает

Answer 6

Я бы использовал следующую функцию для их сортировки

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), то он продолжил бы цепочку вниз.

Имеет смысл?