Count of elements from the array

Question

I am counting the element from array, which is greater then the given element (k)

 // Java implementation of the approach class GFG { // Function to return the count of elements // from the array which are greater than k static int countGreater(int arr[], int n, int k) //arr-array, n-array length, k-number { //here first I sorted array int l = 0; int r = n - 1; // Stores the index of the left most element // from the array which is greater than k int leftGreater = n; // Finds number of elements greater than k while (l <= r) { int m = l + (r - l) / 2; // If mid element is greater than // k update leftGreater and r if (arr[m] > k) { leftGreater = m; r = m - 1; } // If mid element is less than // or equal to k update l else l = m + 1; } // Return the count of elements greater than k return (n - leftGreater); }

I solved with comparing only one number, but what if I have an array to compare with

Sort arr2 and use the previous leftGreaterThan as the starting left value of your binary search for each k in arr2? — RaffleBuffle
– RaffleBuffle, Commented Jun 29, 2021 at 18:54
Why not loop through the array and just count the elements that are greater than k? That way you don't have to sort the array. Sometimes the answer doesn't have to be difficult. — NomadMaker
– NomadMaker, Commented Jun 29, 2021 at 23:03

Valery · Accepted Answer · 2021-06-30 06:03:24Z

There is a varying solutions. So, I can show you several.

First of all, you don't need properties that store the length of an array. You have to do that in C/C++, but not in Java.

Here are some solutions:

A simple solution

private static int[] countGreater(int[] arr, int[] arr2) { int walkThroughArrayLength = arr2.length; int[] result = new int[walkThroughArrayLength]; for (int i = 0; i < walkThroughArrayLength; i++) { int counter = 0; for (int a1 : arr) { if (a1 > arr2[i]) { counter++; } } result[i] = counter; } return result; }

Solution with Stream API

private static int[] countGreater(int[] arr, int[] arr2) { return Arrays.stream(arr2) .map(a2 -> (int) Arrays.stream(arr) .filter(a1 -> a1 > a2) .count()) .toArray(); }

RaffleBuffle · Accepted Answer · 2021-06-29 22:50:52Z

A simple O(nk) solution would be to go through arr for each number in arr2 and count the number of values that are greater.

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k) { int[] res = new int[arr2.length]; for(int i=0; i<k; i++) { int count = 0; for(int v : arr) if(v > arr2[i]) count++; res[i] = count; } return res; }

However, we can do better than this by extending the method you've already identified - sorting arr and using binary search to identify the position of each value in arr2. If arr2 is also sorted then we can use the previously identified position as the initial left-hand edge of our binary search, since we know that subsequent elements in arr2 have to be greater than the current value.

Here's some Java code to illustrate:

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k) { Collections.sort(Arrays.asList(arr)); // assume arr2 is sorted, otherwise results could be out of order int[] res = new int[arr2.length]; for(int i=0, pos=0; i<k; i++) { pos = 1 + Arrays.binarySearch(arr, pos, n, arr2[i]); if(pos < 0) pos = -pos; res[i] = n - pos; } return res; }

I've simplified the code quite a bit by making use of the Arrays.binarySearch method.

For small values of n and k the simple approach will probably be faster, but as they grow the binarySearch approach will take over, despite the cost of the initial sort.

Obinna Nnamani · Accepted Answer · 2021-06-29 19:51:02Z

This is easier when stream is used. You can simply do

public static long countGreater(int[] arr, int k) { IntStream stream = IntStream.of(arr); long count = stream.filter(number -> number > k).count(); return count; }

Collectives™ on Stack Overflow

Count of elements from the array

3 Answers 3

2 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Related