Като се има предвид масив от отделни цели числа ARR [] a надмина на елемент arr [i] е всеки елемент arr [j], така че j> i и arr [j]> arr [i]. Намерете броя на надминателите за всеки елемент в масива.
Примери:
Вход: arr [] = [2 7 5 3 8 1]
Резултат: [4 1 1 1 0 0]
Обяснение: За 2 има 4 по -големи елемента вдясно: [7 5 3 8]
За 7 има 1 по -голям елемент вдясно: [8]
За 5 има 1 по -голям елемент вдясно: [8]
За 3 има 1 по -голям елемент вдясно: [8]
За 8 няма по -голям елемент вдясно: [0]
За 1 няма по -голям елемент вдясно: [0]Вход: arr [] = [4 5 1]
Резултат: [1 0 0]
Обяснение: За 4 има 1 по -голям елемент вдясно: [5]
За 5 няма по -голям елемент вдясно: [0]
За 1 няма по -голям елемент вдясно: [0]
Съдържание
- [Наивен подход] - Използване на две вложени бримки - O (n^2) време и o (1) пространство
- [Очакван подход] - Използване на стъпка на сливане на сортиране - O (n log n) време и o (n) пространство
[Наивен подход] - Използване на две вложени бримки - O (n^2) време и o (1) пространство
Най -простият подход е да повтаря през масива и за всеки елемент Брой броя на елементите към неговите Точно това е по -голямо отколкото.
C++#include
#include
import java.util.ArrayList; class GfG { static ArrayList<Integer> findSurpasser(int[] arr) { int n = arr.length; // List to store surpasser counts ArrayList<Integer> res = new ArrayList<>(); for (int i = 0; i < n; i++) { // Find surpasser for arr[i] int count = 0; for (int j = i + 1; j < n; j++) { if (arr[j] > arr[i]) count++; } res.add(count); } return res; } public static void main(String[] args) { int[] arr = {2 7 5 3 8 1}; ArrayList<Integer> res = findSurpasser(arr); for (int count : res) System.out.print(count + ' '); } }
def findSurpasser(arr): n = len(arr) # List to store surpasser counts res = [0] * n for i in range(n): # Find surpasser for arr[i] count = 0 for j in range(i + 1 n): if arr[j] > arr[i]: count += 1 res[i] = count return res if __name__ == '__main__': arr = [2 7 5 3 8 1] result = findSurpasser(arr) for val in result: print(val end=' ')
using System; using System.Collections.Generic; class GfG { static List<int> findSurpasser(int[] arr) { int n = arr.Length; // List to store surpasser counts List<int> res = new List<int>(); for (int i = 0; i < n; i++) { // Find surpasser for arr[i] int count = 0; for (int j = i + 1; j < n; j++) { if (arr[j] > arr[i]) count++; } res.Add(count); } return res; } static void Main(string[] args) { int[] arr = { 2 7 5 3 8 1 }; List<int> result = findSurpasser(arr); foreach (int count in result) Console.Write(count + ' '); } }
function findSurpasser(arr) { const n = arr.length; // array to store surpasser counts let res = new Array(n).fill(0); for (let i = 0; i < n; i++) { // Find surpasser for arr[i] let count = 0; for (let j = i + 1; j < n; j++) { if (arr[j] > arr[i]) count++; } res[i] = count; } return res; } // Driver Code const arr = [2 7 5 3 8 1]; const result = findSurpasser(arr); console.log(result.join(' '));
Изход
4 1 1 1 0 0
[Очакван подход] - Използване на стъпка на сливане на сортиране - O (n log n) време и o (n) пространство
В този подход използваме Стъпка на сливане на Разходки . По време на сливането, ако ith Елемент в лявата половина е по -малък отколкото jth елемент в дясната половина, това означава, че всички останал Елементи в дясната половина (от j до края) са по -голямо отколкото ith елемент в лявата половина (тъй като и двете половини са сортирани ). Затова добавяме броя на останалите елементи В дясната половина до надхвърлете броя на ith елемент на лявата половина. Този процес се повтаря за всички елементи в лявата половина, тъй като те са обединени с дясната половина.
Тъй като всички елементи в масива са различен Използваме a Hash карта За да запазите броя на надминаването за всеки елемент. След завършването на сорта за сливане, ние попълваме масива на резултатите с броя на надминаването, поддържащ същия ред като оригиналния вход.
C++
#include
import java.util.List; import java.util.Map; import java.util.HashMap; import java.util.ArrayList; class GfG { // Merge function to sort the array // and update surpasser counts static void merge(int[] arr int lo int mid int hi Map<Integer Integer> m) { int n1 = mid - lo + 1; int n2 = hi - mid; int[] left = new int[n1]; int[] right = new int[n2]; // Copy data into temporary arrays left[] and right[] for (int i = 0; i < n1; i++) left[i] = arr[lo + i]; for (int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j]; int i = 0 j = 0 k = lo; // Merging two halves while (i < n1 && j < n2) { // All elements in right[j..n2] are greater than left[i] // So add n2 - j to surpasser count of left[i] if (left[i] < right[j]) { m.put(left[i] m.getOrDefault(left[i] 0) + n2 - j); arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } // Copy remaining elements of left[] if any while (i < n1) arr[k++] = left[i++]; // Copy remaining elements of right[] if any while (j < n2) arr[k++] = right[j++]; } static void mergeSort(int[] arr int lo int hi Map<Integer Integer> m) { if (lo < hi) { int mid = lo + (hi - lo) / 2; // Sort left and right halves mergeSort(arr lo mid m); mergeSort(arr mid + 1 hi m); // Merge them merge(arr lo mid hi m); } } static ArrayList<Integer> findSurpasser(int[] arr) { int n = arr.length; // Map to store surpasser counts Map<Integer Integer> m = new HashMap<>(); // Duplicate array to perform merge sort int[] dup = arr.clone(); mergeSort(dup 0 n - 1 m); // Store surpasser counts in result list ArrayList<Integer> res = new ArrayList<>(); for (int i = 0; i < n; i++) res.add(m.getOrDefault(arr[i] 0)); return res; } public static void main(String[] args) { int[] arr = {2 7 5 3 8 1}; ArrayList<Integer> res = findSurpasser(arr); for (int count : res) System.out.print(count + ' '); } }
def merge(arr lo mid hi m): n1 = mid - lo + 1 n2 = hi - mid left = arr[lo:lo+n1] right = arr[mid+1:mid+1+n2] i = j = 0 k = lo # Merging two halves while i < n1 and j < n2: # All elements in right[j..n2] are greater than left[i] # So add n2 - j in surpasser count of left[i] if left[i] < right[j]: m[left[i]] += n2 - j arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 k += 1 # Copy remaining elements of left[] if any while i < n1: arr[k] = left[i] i += 1 k += 1 # Copy remaining elements of right[] if any while j < n2: arr[k] = right[j] j += 1 k += 1 def mergeSort(arr lo hi m): if lo < hi: mid = lo + (hi - lo) // 2 # Sort left and right half mergeSort(arr lo mid m) mergeSort(arr mid + 1 hi m) # Merge them merge(arr lo mid hi m) def findSurpasser(arr): n = len(arr) # Map to store surpasser counts m = {key: 0 for key in arr} # Duplicate array to perform merge Sort # so that original array is not modified dup = arr[:] mergeSort(dup 0 n - 1 m) # Store surpasser counts in result array # in the same order as given array res = [m[arr[i]] for i in range(n)] return res if __name__ == '__main__': arr = [2 7 5 3 8 1] result = findSurpasser(arr) for val in result: print(val end=' ')
using System; using System.Collections.Generic; class GfG { // Merge function to sort the array // and update surpasser counts static void merge(int[] arr int lo int mid int hi Dictionary<int int> m) { int n1 = mid - lo + 1; int n2 = hi - mid; int[] left = new int[n1]; int[] right = new int[n2]; // Copy data into temporary arrays for (int i = 0; i < n1; i++) left[i] = arr[lo + i]; for (int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j]; int i1 = 0 j1 = 0 k = lo; // Merge the two halves while (i1 < n1 && j1 < n2) { // Count surpassers if (left[i1] < right[j1]) { if (!m.ContainsKey(left[i1])) m[left[i1]] = 0; m[left[i1]] += n2 - j1; arr[k++] = left[i1++]; } else { arr[k++] = right[j1++]; } } // Copy remaining elements while (i1 < n1) arr[k++] = left[i1++]; while (j1 < n2) arr[k++] = right[j1++]; } static void mergeSort(int[] arr int lo int hi Dictionary<int int> m) { if (lo < hi) { int mid = lo + (hi - lo) / 2; // Recursive sort mergeSort(arr lo mid m); mergeSort(arr mid + 1 hi m); // Merge sorted halves merge(arr lo mid hi m); } } static List<int> findSurpasser(int[] arr) { int n = arr.Length; Dictionary<int int> m = new Dictionary<int int>(); int[] dup = new int[n]; Array.Copy(arr dup n); mergeSort(dup 0 n - 1 m); List<int> res = new List<int>(); for (int i = 0; i < n; i++) { res.Add(m.ContainsKey(arr[i]) ? m[arr[i]] : 0); } return res; } static void Main() { int[] arr = {2 7 5 3 8 1}; List<int> res = findSurpasser(arr); foreach (int count in res) Console.Write(count + ' '); } }
function merge(arr lo mid hi m) { const n1 = mid - lo + 1; const n2 = hi - mid; const left = []; const right = []; // Copy data into temporary arrays left[] and right[] for (let i = 0; i < n1; i++) left[i] = arr[lo + i]; for (let j = 0; j < n2; j++) right[j] = arr[mid + 1 + j]; let i = 0 j = 0 k = lo; // Merging two halves while (i < n1 && j < n2) { // All elements in right[j..n2] are greater than left[i] // So add n2 - j in surpasser count of left[i] if (left[i] < right[j]) { m[left[i]] = (m[left[i]] || 0) + n2 - j; arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } // Copy remaining elements of left[] if any while (i < n1) arr[k++] = left[i++]; // Copy remaining elements of right[] if any while (j < n2) arr[k++] = right[j++]; } function mergeSort(arr lo hi m) { if (lo < hi) { const mid = Math.floor(lo + (hi - lo) / 2); // Sort left and right half mergeSort(arr lo mid m); mergeSort(arr mid + 1 hi m); // Merge them merge(arr lo mid hi m); } } function findSurpasser(arr) { const n = arr.length; // Map to store surpasser counts const m = {}; // Duplicate array to perform merge Sort // so that original array is not modified const dup = arr.slice(); mergeSort(dup 0 n - 1 m); // Store surpasser counts in result array // in the same order as given array const res = []; for (let i = 0; i < n; i++) res.push(m[arr[i]] || 0); return res; } // Driver Code const arr = [2 7 5 3 8 1]; const res = findSurpasser(arr); console.log(res.join(' '));
Изход
4 1 1 1 0 0
Свързани статии:
java колекции
- Брой на инверсията
- Разходки