Сегодня (27–11–22) мой 42-й день программирования. сегодня решил 2 вопроса
Задача 1: K-й наименьший элемент
Учитывая массив arr[] и целое число K, где K меньше размера массива, задача состоит в том, чтобы найти K-й наименьший элемент в заданный массив. Дано, что все элементы массива различны.
Пример 1:
Input: N = 6 arr[] = 7 10 4 3 20 15 K = 3 Output : 7 Explanation : 3rd smallest element in the given array is 7.
Пример 2:
Input: N = 5 arr[] = 7 10 4 20 15 K = 4 Output : 15 Explanation : 4th smallest element in the given array is 15.
Ваша задача:
Вам не нужно ничего читать или печатать. Ваша задача — выполнить функцию kthSmallest(), которая принимает массив arr[], целые числа l и r. обозначая начальный и конечный индекс массива и целое число K в качестве входных данных, и возвращает Kth наименьший элемент.
Решение (в Java):
class Solution{ public static int kthSmallest(int[] arr, int l, int r, int k) { Arrays.sort(arr); if(l<r){ if(l==0) return arr[k-1]; else return arr[l+k-1]; } else return 0; } }
Проблема 2: Сортировка массива из 0, 1 и 2 без использования Arrays.sort()
Дан массив размера N, содержащий только 0, 1 и 2; отсортировать массив в порядке возрастания.
Пример 1:
Input: N = 5 arr[]= {0 2 1 2 0} Output: 0 0 1 2 2 Explanation: 0s 1s and 2s are segregated into ascending order.
Пример 2:
Input: N = 3 arr[] = {0 1 0} Output: 0 0 1 Explanation: 0s 1s and 2s are segregated into ascending order.
Ваша задача:
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию sort012(), которая принимает массив arr и N в качестве входных параметров и сортирует массив на месте.
Ожидаемая временная сложность:O(N)
Ожидаемое вспомогательное пространство: O(1)
Решение (в Java):
class Solution { public static void sort012(int a[], int n) { int i=0; int zero=0, one=0, two=0; while(i<n){ if(a[i]==0) zero++; else if(a[i]==1) one++; else two+=2; i++; } for(i=0; i<zero; i++) a[i]=0; for(i=zero; i<zero+one; i++) a[i]=1; for(i=zero+one; i<n; i++) a[i]=2; }