Java 中右侧较小元素的计数

2024 年 9 月 26 日 | 阅读 16 分钟

给定一个包含数字（可以是负数或正数）的数组或列表 inArr。任务是找出当前元素右侧有多少个较小的元素。以下示例有助于更好地理解。

示例 1

输入

int inArr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8}

输出： outArr[] = {7, 4, 7, 1, 2, 2, 0, 1, 0, 0}

解释： 对于元素 7，右侧的较小数目是 7（4、1、3、5、0、6、2）。对于元素 4，右侧的较小数目是 4（1、3、0、2）。数字 9 右侧的所有元素都比 9 小，其计数为 7。对于元素 1，右侧只有一个 0 比它小。因此，计数为 1。对于 3，右侧只有两个元素（0、2）比它小。对于元素 5，右侧只有 0 和 2 比 5 小。对于 0，没有较小的元素。因此，计数为 0。对于 6，只有 2 比 6 小（计数为 1）。对于元素 2，右侧只有 8，它比 2 大。因此，计数为 0。对于元素 8，右侧没有元素，计数为 0。

示例 2

输入

int inArr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

输出： outArr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

解释： 所有元素都按严格递减的顺序排列。此外，输入数组中元素的排列方式使得右侧元素的数量等于元素本身的值。例如，元素 1 右侧的元素数量为 1（右侧只有 0）。因此，输入数组本身就是答案。

示例 3

输入

int inArr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

输出： outArr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

解释： 元素按递增顺序排列。因此，如果我们以输入数组的元素为参考，则右侧没有较小的元素。因此，输出数组只包含 0。

示例 4

输入

int inArr[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

输出： outArr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

解释： 输入数组的所有元素都是相同的，即值相同。因此，输入数组中不存在较小的元素。因此，输出数组的所有元素都为零。

方法：使用嵌套循环

在此方法中，我们将嵌套两个 for 循环。外层循环选择输入数组中的一个元素（将其视为当前元素）。内层循环从当前元素的下一个元素开始，一直遍历到末尾。在内层循环中，将内层循环变量指向的元素与当前元素进行比较。如果它较小，则将当前元素的计数加 1；否则，不增加计数。

文件名： CountSmallEle.java

// important import statements
import java.util.ArrayList;
import java.util.Arrays;

public class CountSmallEle 
{

public ArrayList<Integer> computeSmallEleNum(ArrayList<Integer> inArr, int s) 
{   
ArrayList<Integer> outArr = new ArrayList<Integer>();

// outer loop picks the current element
for(int i = 0; i < s; i++)
{
// for keeping the count of the elements
// that is smaller than the current element
// and are occurring on the right side
int count = 0;
for(int j = i + 1; j < s; j++)
{
if(inArr.get(i) > inArr.get(j))
{
// smaller element on the right side
// is found. Hence, increasing the 
// count by 1
count = count + 1;
}
}

// adding the count for the current element
outArr.add(count);
}


// returning the output list
return outArr;
}
    
// main method
public static void main(String argvs[])
{
// creating an object of the class CountSmallEle 
CountSmallEle obj = new CountSmallEle();

// input 1
ArrayList<Integer> inArr = new ArrayList<Integer>
(
Arrays.asList(7, 4, 9, 1, 3, 5, 0, 6, 2, 8)
);

// computing the size of the 
// input array
int size = inArr.size();
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();
ArrayList<Integer> ans = obj.computeSmallEleNum(inArr, size);

System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < size; i++)
{
System.out.print(ans.get(i) + " ");
}

System.out.println( "\n" );

// input 2
inArr = new ArrayList<Integer>
(
Arrays.asList(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeSmallEleNum(inArr, size);

System.out.println("The count of the smaller element on the right side is: ");

for(int i = 0; i < size; i++)
{
System.out.print(ans.get(i) + " ");
}

System.out.println( "\n" );

// input 3
inArr = new ArrayList<Integer>
(
Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeSmallEleNum(inArr, size);

System.out.println("The count of the smaller element on the right side is: ");

for(int i = 0; i < size; i++)
{
System.out.print(ans.get(i) + " ");
}

System.out.println( "\n" );


// input 4
inArr = new ArrayList<Integer>
(
Arrays.asList(4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeSmallEleNum(inArr, size);

System.out.println("The count of the smaller element on the right side is: ");

for(int i = 0; i < size; i++)
{
System.out.print(ans.get(i) + " ");
}

}

}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The count of the smaller element on the right side is: 
7 4 7 1 2 2 0 1 0 0 

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The count of the smaller element on the right side is: 
9 8 7 6 5 4 3 2 1 0 

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0 

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0

复杂度分析： 由于程序使用了嵌套循环，因此程序的时间复杂度为 O(N^2)。程序还使用了额外的空间来存储输出。因此，程序的空间复杂度也为 O(N)，其中 N 是输入数组中存在的元素总数。

方法：使用带有附加字段的 BST

另一种方法是使用具有附加字段的简单二叉搜索树 (BST)。这两个附加字段是：1) 用于存储节点左侧的元素，2) 用于存储元素的出现次数。我们将从后往前遍历给定数组，并将元素添加到二叉搜索树中。在将元素添加到二叉搜索树时，我们将计算小于当前元素的所有元素的数量。

实施

观察下面的程序。

文件名： CountSmallEle1.java

// important import statement
import java.util.*;

public class CountSmallEle1
{
static Node rt = null;

// A Node class
static class Node
{
int val;
int count;
Node lft;
Node rght;

// Constructor of the class Node
Node(int n1, int n2)
{
this.val = n1;
this.count = n2;
this.lft = null;
this.rght = null;
}

}

public int computeSmallEleNum(Node rt, int val, int cntSmaller)
{

// Handling the base case
if (rt == null)
{
rt = new Node(val, 0);
return cntSmaller;
}
if (rt.val < val)
{
if(rt.rght != null)
{
return rt.count + computeSmallEleNum(rt.rght, val, cntSmaller + 1);
}
// if the control reaches here, then it
// means the right side node does not exist.
// Therefore, we will create one with the given value
rt.rght = new Node(val, 0);

return rt.count + cntSmaller + 1;
}
else
{
rt.count = rt.count + 1;
if(rt.lft != null)
{
return computeSmallEleNum(rt.lft, val, cntSmaller);
}
// if the control reaches here, then it
// means the left side node does not exist.
// Therefore, we will create one with the given value
rt.lft = new Node(val, 0);
return cntSmaller;
}
}

// Driver code
public static void main(String[] args)
{
// input 1
int arr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8};

// computing the size of the input array
int n = arr.length;

// auxiliary array for storing the 
// answer
int ans[] = new int[n];

// creating an object of the class CountSmallEle1
CountSmallEle1 obj = new CountSmallEle1();

// The last element of the input array is 
// the root node. Since no element exists
// after the last element. The smaller element
// count for the last element is zero.
obj.rt = new Node(arr[n - 1], 0);

// computing answer for the rest of the other elements
for(int i = n - 2; i >= 0; i--)
{
ans[i] = obj.computeSmallEleNum(obj.rt, arr[i], 0);
}

System.out.println("For the input array: ");

for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans[i] + " ");
}

System.out.println( "\n" );

// input 2
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

// computing the size of the input array
n = arr1.length;

// auxiliary array for storing the 
// answer
int ans1[] = new int[n];

// The last element of the input array is 
// the root node. Since no element exists
// after the last element. The smaller element
// count for the last element is zero.
obj.rt = new Node(arr1[n - 1], 0);

// computing answer for the rest of the other elements
for(int i = n - 2; i >= 0; i--)
{
ans1[i] = obj.computeSmallEleNum(obj.rt, arr1[i], 0);
}
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans1[i] + " ");
}

System.out.println( "\n" );


// input 3
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// computing the size of the input array
n = arr2.length;

// auxiliary array for storing the 
// answer
int ans2[] = new int[n];

// The last element of the input array is 
// the root node. Since no element exists
// after the last element. The smaller element
// count for the last element is zero.
obj.rt = new Node(arr2[n - 1], 0);

// computing answer for the rest of the other elements
for(int i = n - 2; i >= 0; i--)
{
ans2[i] = obj.computeSmallEleNum(obj.rt, arr2[i], 0);
}
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr2[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans2[i] + " ");
}

System.out.println( "\n" );
// input 4
int arr3[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
// computing the size of the input array
n = arr3.length;
// auxiliary array for storing the 
// answer
int ans3[] = new int[n];
// The last element of the input array is 
// the root node. Since no element exists
// after the last element. The smaller element
// count for the last element is zero.
obj.rt = new Node(arr3[n - 1], 0);

// computing answer for the rest of the other elements
for(int i = n - 2; i >= 0; i--)
{
ans3[i] = obj.computeSmallEleNum(obj.rt, arr3[i], 0);
}
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr3[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans3[i] + " ");
}
}
}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The count of the smaller element on the right side is: 
7 4 7 1 2 2 0 1 0 0 

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The count of the smaller element on the right side is: 
9 8 7 6 5 4 3 2 1 0 

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0 

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0

复杂度分析： 由于添加的步骤可能需要 O(n) 时间，因此程序的时间复杂度为 O(n^2)。程序还使用辅助数组来存储结果，这使得程序的空间复杂度为 O(n)，其中 n 是数组中存在的元素总数。

我们可以进行优化以降低时间复杂度。以下方法展示了这一点。

方法：使用自平衡树

BST 的缺点是它不是自平衡树。因此，BST 可能会变成倾斜树，导致时间复杂度较高。因此，为了进一步优化，需要使用自平衡树来计算答案。

我们将通过从右到左遍历输入数组，逐个将所有元素插入自平衡树。每当插入一个新键时，我们将其与根元素（输入数组的最右侧元素）进行检查或比较。如果新键大于根，则意味着它大于根节点左侧的所有节点。因此，左子树的大小会添加到新插入键的较小数目的计数中。其他节点也遵循相同的方法。

实施

观察下面的程序。

文件名： CountSmallEle1.java

// important import statement
import java.util.*;
public class CountSmallEle1
{
// An AVL tree node
static class AVLNode
{
	int key;
	AVLNode lft;
	AVLNode rght;
	int hght;

	// size of the rooted tree 
	int s;
};

// A method for finding the height of 
// the tree rooted with r
static int height(AVLNode r)
{
	if (r == null)
	{
	return 0;
	}
	return r.hght;
}
// A method for size of the
// tree of rooted with r
static int size(AVLNode r)
{
	if (r == null)
	{
	    return 0;
	}

	return r.s;
}
// A Method for finding the maximum
// between p and q
static int findMax(int p, int q)
{
	return (p > q) ? p : q;
}
// Helper Method for allocating the
// new node with the provided key. The method
// assigns a null value to the right and left pointers.
static AVLNode newNode(int key)
{
	AVLNode nde = new AVLNode();
	nde.key = key;
	nde.lft = null;
	nde.rght = null;

	// At leaf, the new node is added at
	// the beginning
	nde.hght = 1;
	nde.s = 1;
	return(nde);
}
// A method for doing the right rotation of the 
// subtree rooted with r
static AVLNode rightRotate(AVLNode r)
{
	AVLNode nde = r.lft;
	AVLNode T2 = nde.rght;

	// Perform rotation
	nde.rght = r;
	r.lft = T2;

	// Update heights
	r.hght = Math.max(height(r.lft), height(r.rght)) + 1;
	nde.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;

	// Updating the sizes
	r.s = size(r.lft) + size(r.rght) + 1;
	nde.s = size(nde.lft) + size(nde.rght) + 1;
	// Updating the sizes
	r.s = size(r.lft) + size(r.rght) + 1;
	nde.s = size(nde.lft) + size(nde.rght) + 1;

	// Returning the new root
	return nde;
}

// A utility method for the left rotation of the 
// subtree rooted with r
public AVLNode leftRotate(AVLNode r)
{
	AVLNode nde = r.rght;
	AVLNode T2 = nde.lft;

	// Performing the rotation
	nde.lft = r;
	r.rght = T2;

	// Update heights
	r.hght = Math.max(height(r.lft), height(r.rght)) + 1;
	r.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;

	// Update sizes
	r.s = size(r.lft) + size(r.rght) + 1;
	nde.s = size(nde.lft) + size(nde.rght) + 1;

	// Returning the new root
	return nde;
}
// Getting the Balance factor of the node r
public int getBalance(AVLNode r)
{
	if (r == null)
	{
	return 0;
	}

	return height(r.lft) - height(r.rght);
}

// The method inserts a new key into the AVL tree rooted with
// the node. Also, updating the count for fetching count
// of the lesser elements with the new key
public AVLNode insert(AVLNode nde, int cntSmaller[], int key, int cnt)
{
	// Performing the rotation of the BST (normal)
	if (nde == null)
	{
	return(newNode(key));
	}

	if (key < nde.key)
	{
	nde.lft = insert(nde.lft, cntSmaller, key, cnt);
	}
	else if(key > nde.key)
	{
	nde.rght = insert(nde.rght, cntSmaller, key, cnt);
	// updating the count of the lesser elementes than the key
	cntSmaller[cnt] = cntSmaller[cnt] + size(nde.lft) + 1;
	}
	
	// the key value is same as the nde value
	// hence, that key value should not be inserted
	else
	{
	    return nde;
	}


	// Updating the size and the height of this ancestor node
	nde.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;
	nde.s = size(nde.lft) + size(nde.rght) + 1;

	// Getting the balance factor of the 
	// ancestor node for checking whether the
	// node has become unbalanced or not
	int balanceFactor = getBalance(nde);

	// If the node gets unbalanced,
	// then we have the 4 cases to consider

	// Handling the Left-Left Case
	if (balanceFactor > 1 && key < nde.lft.key)
	{
	return rightRotate(nde);
	}

	// Handling the Right-Right Case
	if (balanceFactor < -1 && key > nde.rght.key)
	{
	return leftRotate(nde);
	}
	// Handling the Left-Right Case
	if (balanceFactor > 1 && key > nde.lft.key)
	{
	nde.lft = leftRotate(nde.lft);
	return rightRotate(nde);
	}

	// handling the Right-Left Case
	if (balanceFactor < -1 && key < nde.rght.key)
	{
	nde.rght = rightRotate(nde.rght);
	return leftRotate(nde);
	}

	// Returning the node pointer that is unchanged
	return nde;
}

// The following method is used to update the
// cntSmaller array for containing the count of
// the smaller elements on the right side.
public void constructLowerArr(int arr[], int cntSmaller[], int size)
{
	AVLNode rt = null;

	// Initializing all of the counts in
	// the cntSmaller array with the value 0
	for(int j = 0; j < size; j++)
	{
	    cntSmaller[j] = 0;
	}

	// Beginning from the rightmost element,
	// put all of the elements one by one in
	// the AVL tree 
	for(int i = size - 1; i >= 0; i--)
	{
	rt = insert(rt, cntSmaller, arr[i], i);
	}
}


// Driver code
public static void main(String[] args)
{
// input 1
int arr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8};

// computing the size of the input array
int n = arr.length;

// auxiliary array for storing the 
// answer
int ans[] = new int[n];

// creating an object of the class CountSmallEle1
CountSmallEle1 obj = new CountSmallEle1();
obj.constructLowerArr(arr, ans, n);
System.out.println("For the input array: ");

for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans[i] + " ");
}

System.out.println( "\n" );

// input 2
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

// computing the size of the input array
n = arr1.length;

// auxiliary array for storing the 
// answer
int ans1[] = new int[n];

obj.constructLowerArr(arr1, ans1, n);

System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans1[i] + " ");
}

System.out.println( "\n" );


// input 3
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// computing the size of the input array
n = arr2.length;

// auxiliary array for storing the 
// answer
int ans2[] = new int[n];

obj.constructLowerArr(arr2, ans2, n);

System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr2[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans2[i] + " ");
}

System.out.println( "\n" );


// input 4
int arr3[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4};

// computing the size of the input array
n = arr3.length;

// auxiliary array for storing the 
// answer
int ans3[] = new int[n];

obj.constructLowerArr(arr3, ans3, n);

System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr3[i] + " ");
}
System.out.println();
System.out.println("The count of the smaller element on the right side is: ");
for(int i = 0; i < n; i++)
{
System.out.print(ans3[i] + " ");
}

}


}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The count of the smaller element on the right side is: 
7 4 7 1 2 2 0 1 0 0 

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The count of the smaller element on the right side is: 
9 8 7 6 5 4 3 2 1 0 

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0 

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The count of the smaller element on the right side is: 
0 0 0 0 0 0 0 0 0 0

复杂度分析： 上述程序中使用的二叉树永远不会是倾斜树。因此，程序的时间复杂度为 O(n x log(n))，其中 n 是输入数组中存在的节点总数。程序的空间复杂度与上一个程序相同。

下一个主题Java 中的字符串交错问题

Java 中右侧较小元素的计数

方法：使用嵌套循环

方法：使用带有附加字段的 BST

实施

方法：使用自平衡树

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中右侧较小元素的计数

方法：使用嵌套循环

方法：使用带有附加字段的 BST

实施

方法：使用自平衡树

实施

相关帖子

打印数组元素的 Java 程序

Java 计算字符串中字符总数的程序

Duck Number Java

查找具有 N 个键的可能二叉搜索树总数的 Java 程序

如何在 Java 中将 char 转换为 int

Java 中的冒泡排序

不使用第三个或临时变量交换两个字符串变量的 Java 程序。

Java 在循环链表末尾插入新节点的程序

如何在 Java 中将十进制转换为八进制

Java 计算矩阵每行每列之和的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器