Благородное число (Noble integer)

-
Задача. Дан целочисленный массив. Найти целое число p, если оно существует, такое, что количество элементов массива, которые больше, чем p, равно (количество таких элементов) p

Если число существует, вернуть 1, иначе вернуть -1.

Идея решения. Поскольку речь идёт об отношениях больше-меньше между всеми элементами, то имеет смысл отсортировать исходный массив.


Затем нужно просматривать каждый эелемент массива (пропуская его дубликаты) и сравнивать, сколько элементов (больше его) ещё остались до конца массива. если число оставшихся элементов равно самому (в настоящий момент рассматриваемому) элементу, то мы нашли благородное число.

public class Solution {
    public int solve(ArrayList<Integer> A) {
        // Total runtime: O(n log n) due to sort
        Collections.sort(A);
        
        for(int i = 0; i < A.size(); i++) {
            // Пропускаем все дубликаты
            if(i < A.size() - 1 && A.get(i) == A.get(i + 1)) {
                continue;
            }
            // Условие, при котором задача решена
            if(A.size() - i - 1 == A.get(i)) {
                return 1;
            }
        }
        
        return -1;
    }
}

Данный алгоритм можно ускорить, если ввести проверку: 
if(A.size() - i - 1 < A.get(i)) { return -1; }
Если осталось элементов меньше, чем рассматриваемое число, мы уже ничего и не "словим" в этом массиве - можно выходить.

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

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

-
Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...
Далее...

Число подмассивов, в которых сумма элементов равна k

-
Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...
Далее...

Сложить два числа, которые представлены списком

-
Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка. Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0. Пример: Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4) Резальтат: 7 -> 0 -> 8 Пояснение: 342 + 465 = 807. Идея решения. В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик. Имплементация. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка     ListNode p = l1, q = l2, curr = dummyHead;     int carry = 0;     while (p != null || q != null) {         int x = (p != null) ? p.v...
Далее...