Pateikė daugybę atskirų sveikųjų skaičių ARR [] a peržengti elemento arr [i] yra bet kuris elementas arr [j] toks, kad j> i ir arr [j]> arr [i]. Raskite kiekvieno masyvo elemento viršūnių skaičių.
masyvo sąrašas surūšiuotas java
Pavyzdžiai:
Įvestis: arr [] = [2 7 5 3 8 1]
Išvestis: [4 1 1 1 0 0]
Paaiškinimas: 2 jo dešinėje yra 4 didesni elementai: [7 5 3 8]
7 jo dešinėje yra 1 didesnis elementas: [8]
5 jo dešinėje yra 1 didesnis elementas: [8]
3 atveju yra 1 didesnis elementas dešinėje: [8]
8 jo teisė nėra didesnio elemento: [0]
1 už jo teisę nėra didesnio elemento: [0]Įvestis: arr [] = [4 5 1]
Išvestis: [1 0 0]
Paaiškinimas: 4 jo dešinėje yra 1 didesnis elementas: [5]
5 už jo teisę nėra didesnio elemento: [0]
1 už jo teisę nėra didesnio elemento: [0]
Turinio lentelė
mvc su java
[Naivus požiūris] - naudojant dvi įdėtas kilpas - o (n^2) laikas ir o (1) erdvė
Paprasčiausias požiūris yra kartoti per masyvą ir kiekvieną elementą skaičiavimas elementų skaičius jo Teisingai tai yra didesnis nei tai.
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(' '));
Išvestis
4 1 1 1 0 0
[Tikimas
Taikant šį požiūrį naudojame sujungti žingsnį iš Pasivaikščiojimai . Sujungimo metu, jei ITH Elementas kairėje pusėje yra mažesnis nei JTH elementas dešinėje pusėje tai reiškia, kad viskas likęs elementai dešinėje pusėje (nuo J iki pabaigos) yra didesnis nei ITH Elementas kairėje pusėje (nes abi pusės yra Rūšiuotas ). Todėl pridedame skaičių likę elementai dešinėje pusėje iki peržengti skaičių iš ITH Kairiosios pusės elementas. Šis procesas pakartojamas visiems kairiajai pusei elementams, nes jie yra sujungti su dešine puse.
Kadangi visi masyvo elementai yra skirtingas Mes naudojame a maišos žemėlapis Norėdami išlaikyti kiekvieno elemento viršūnės skaičių. Kai sujungimo rūšiavimas bus baigtas, užpildome rezultatų masyvą su „Surpasser“ skaičiavimais, palaikančiais tą pačią tvarką kaip ir pradinis įvestis.
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(' '));
Išvestis
4 1 1 1 0 0
Susiję straipsniai:
javascript skambinimo funkcija iš html
- Inversijos skaičius
- Pasivaikščiojimai