给定BST的前序遍历。任务是找到少于根的元素数。 例如：
null
Input: preorder[] = {3, 2, 1, 0, 5, 4, 6}Output: 3Input: preorder[] = {5, 4, 3, 2, 1}Output: 4
对于二叉搜索树，前序遍历的形式如下：
根，{根的左子树中的元素}，{根的右子树中的元素}
简单方法：
- 遍历给定的预订单。
- 检查当前元素是否大于根。
- 如果是，则返回 indexOfCurrentElement–1 因为小于root的元素数将是除root之外的currentelement之前出现的所有元素。
C++
// C++ implementation of above approach #include <iostream> using namespace std; // Function to find the first index of the element // that is greater than the root int findLargestIndex( int arr[], int n) { int i, root = arr[0]; // Traverse the given preorder for (i = 0; i < n-1; i++) { // Check if the number is greater than root // If yes then return that index-1 if (arr[i] > root) return i-1; } } // Driver Code int main() { int preorder[] = {3, 2, 1, 0, 5, 4, 6}; int n = sizeof (preorder) / sizeof (preorder[0]); cout << findLargestIndex(preorder, n); return 0; } |
JAVA
// Java implementation of // above approach class GFG { // Function to find the first // index of the element that // is greater than the root static int findLargestIndex( int arr[], int n) { int i, root = arr[ 0 ]; // Traverse the given preorder for (i = 0 ; i < n - 1 ; i++) { // Check if the number is // greater than root // If yes then return // that index-1 if (arr[i] > root) return i- 1 ; } return 0 ; } // Driver Code public static void main(String ags[]) { int preorder[] = { 3 , 2 , 1 , 0 , 5 , 4 , 6 }; int n = preorder.length; System.out.println(findLargestIndex(preorder, n)); } } // This code is contributed // by Subhadeep Gupta |
Python3
# Python3 implementation of above approach # Function to find the first index of # the element that is greater than the root def findLargestIndex(arr, n): i, root = arr[ 0 ], arr[ 0 ]; # Traverse the given preorder for i in range ( 0 , n - 1 ): # Check if the number is greater than # root. If yes then return that index-1 if (arr[i] > root): return i - 1 ; # Driver Code preorder = [ 3 , 2 , 1 , 0 , 5 , 4 , 6 ]; n = len (preorder) print (findLargestIndex(preorder, n)); # This code is contributed # by Akanksha Rai |
C#
// C# implementation of above approach using System; class GFG { // Function to find the first // index of the element that // is greater than the root static int findLargestIndex( int []arr, int n) { int i, root = arr[0]; // Traverse the given preorder for (i = 0; i < n - 1; i++) { // Check if the number is // greater than root. If yes // then return that index-1 if (arr[i] > root) return i - 1; } return 0; } // Driver Code static public void Main() { int []preorder = {3, 2, 1, 0, 5, 4, 6}; int n = preorder.Length; Console.WriteLine(findLargestIndex(preorder, n)); } } // This code is contributed // by Subhadeep Gupta |
PHP
<?php // PHP implementation of above approach // Function to find the first index of // the element that is greater than the root function findLargestIndex( $arr , $n ) { $i ; $root = $arr [0]; // Traverse the given preorder for ( $i = 0; $i < $n - 1; $i ++) { // Check if the number is greater than // root. If yes, then return that index-1 if ( $arr [ $i ] > $root ) return $i - 1; } } // Driver Code $preorder = array (3, 2, 1, 0, 5, 4, 6); $n = count ( $preorder ); echo findLargestIndex( $preorder , $n ); // This code is contributed // by 29AjayKumar ?> |
Javascript
<script> // JavaScript implementation of above approach // Function to find the first index of the element // that is greater than the root function findLargestIndex(arr, n) { var i, root = arr[0]; // Traverse the given preorder for (i = 0; i < n-1; i++) { // Check if the number is greater than root // If yes then return that index-1 if (arr[i] > root) return i-1; } } // Driver Code var preorder = [3, 2, 1, 0, 5, 4, 6]; var n = preorder.length; document.write( findLargestIndex(preorder, n)); </script> |
输出：
3
时间复杂性： O（n） 高效方法（使用二进制搜索） ：这里的想法是利用二进制搜索的扩展形式。步骤如下：
- 转到中间。检查中间的元素是否大于根。如果是，那么我们在数组的左半部分递归。
- 否则，如果mid处的元素小于root，mid+1处的元素大于root，则返回mid作为答案。
- 否则我们在数组的右半部分递归，重复上述步骤。
下面是上述想法的实施。
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to count the smaller elements int findLargestIndex( int arr[], int n) { int root = arr[0], lb = 0, ub = n-1; while (lb < ub) { int mid = (lb + ub)/2; // Check if the element at mid // is greater than root. if (arr[mid] > root) ub = mid - 1; else { // if the element at mid is lesser // than root and element at mid+1 // is greater if (arr[mid + 1] > root) return mid; else lb = mid + 1; } } return lb; } // Driver Code int main() { int preorder[] = {3, 2, 1, 0, 5, 4, 6}; int n = sizeof (preorder) / sizeof (preorder[0]); cout << findLargestIndex(preorder, n); return 0; } |
JAVA
// Java implementation // of above approach import java.util.*; class GFG { // Function to count the // smaller elements static int findLargestIndex( int arr[], int n) { int root = arr[ 0 ], lb = 0 , ub = n - 1 ; while (lb < ub) { int mid = (lb + ub) / 2 ; // Check if the element at // mid is greater than root. if (arr[mid] > root) ub = mid - 1 ; else { // if the element at mid is // lesser than root and // element at mid+1 is greater if (arr[mid + 1 ] > root) return mid; else lb = mid + 1 ; } } return lb; } // Driver Code public static void main(String args[]) { int preorder[] = { 3 , 2 , 1 , 0 , 5 , 4 , 6 }; int n = preorder.length; System.out.println( findLargestIndex(preorder, n)); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of above approach # Function to count the smaller elements def findLargestIndex(arr, n): root = arr[ 0 ]; lb = 0 ; ub = n - 1 ; while (lb < ub): mid = (lb + ub) / / 2 ; # Check if the element at mid # is greater than root. if (arr[mid] > root): ub = mid - 1 ; else : # if the element at mid is lesser # than root and element at mid+1 # is greater if (arr[mid + 1 ] > root): return mid; else : lb = mid + 1 ; return lb; # Driver Code preorder = [ 3 , 2 , 1 , 0 , 5 , 4 , 6 ]; n = len (preorder); print (findLargestIndex(preorder, n)); # This code is contributed by mits |
C#
// C# implementation // of above approach using System; class GFG { // Function to count the // smaller elements static int findLargestIndex( int []arr, int n) { int root = arr[0], lb = 0, ub = n - 1; while (lb < ub) { int mid = (lb + ub) / 2; // Check if the element at // mid is greater than root. if (arr[mid] > root) ub = mid - 1; else { // if the element at mid is // lesser than root and // element at mid+1 is greater if (arr[mid + 1] > root) return mid; else lb = mid + 1; } } return lb; } // Driver Code public static void Main(String []args) { int []preorder = {3, 2, 1, 0, 5, 4, 6}; int n = preorder.Length; Console.WriteLine( findLargestIndex(preorder, n)); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP implementation of above approach // Function to count the smaller elements function findLargestIndex( $arr , $n ) { $root = $arr [0]; $lb = 0; $ub = $n - 1; while ( $lb < $ub ) { $mid = (int)(( $lb + $ub ) / 2); // Check if the element at mid // is greater than root. if ( $arr [ $mid ] > $root ) $ub = $mid - 1; else { // if the element at mid is lesser // than root and element at mid+1 // is greater if ( $arr [ $mid + 1] > $root ) return $mid ; else $lb = $mid + 1; } } return $lb ; } // Driver Code $preorder = array (3, 2, 1, 0, 5, 4, 6); $n = count ( $preorder ); echo findLargestIndex( $preorder , $n ); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript implementation of above approach // Function to count the smaller elements function findLargestIndex(arr, n) { var root = arr[0], lb = 0, ub = n-1; while (lb < ub) { var mid = parseInt((lb + ub)/2); // Check if the element at mid // is greater than root. if (arr[mid] > root) ub = mid - 1; else { // if the element at mid is lesser // than root and element at mid+1 // is greater if (arr[mid + 1] > root) return mid; else lb = mid + 1; } } return lb; } // Driver Code var preorder = [3, 2, 1, 0, 5, 4, 6]; var n = preorder.length; document.write( findLargestIndex(preorder, n)); </script> |
输出：
3
时间复杂性： O（logn）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
