网上看到的面试题目。
93.在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。
直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数,
一个解答:这需要两次遍历,然后再遍历一次原数组,
将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。
给出这个解答后,面试官有要求只能用一个辅助数组,且要求少遍历一次。
下面是试解,当做是抛砖引玉吧。
package javabasic;
import java.util.Arrays;
import java.util.Random;
public class FindBinTreeRoot {
/**
* 在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。
* 这里把数组元素看做是二叉排序树的结点,找出能作为root结点的元素。
* 例如:[4,2,3,5,7,4,8,9],则8或9都可以作为root结点。
* @param arr
* @return 目标元素的索引
*/
public static int find( int[] arr ) {
// init the left max element to MIN. So any element >= it
int lMax = Integer.MIN_VALUE;
for ( int i = 0; i < arr.length; i++ ) {
int cur = arr[i];
if ( cur >= lMax ) {
// update the left max element
lMax = cur;
boolean rightOK = true;
// check if the right elements >= the current element
for ( int j = i + 1; j < arr.length; j++ ) {
// update the left max element
if ( arr[j] >= lMax ) {
lMax = arr[j];
}
if ( arr[j] < cur ) {
// There is a right element < the current element,
// so no element before index j is the possible answer.
rightOK = false;
// Elements after j are possible, so set current element to j
i = j;
break;
}
}
if ( rightOK ) {
// right the target element index
return i;
}
}
}
return -1;
}
/**
* @param args
*/
public static void main( String[] args ) {
// int[] arr = new int[]{4,2,3,5,7,4,8,9};
//随机产生一个20个元素的数组
int[] arr = new int[20];
Random ran = new Random();
int target = ran.nextInt(arr.length);
arr[target] = 10;
for(int i=0;i<target;i++){
//left half <10
arr[i] = ran.nextInt( 10 );
}
for(int i=target + 1;i<arr.length;i++){
//right half > 10
arr[i] = ran.nextInt( 10 ) + 10;
}
System.out.println(Arrays.toString(arr));
System.out.println("target index=" + target);
System.out.println("result index=" + FindBinTreeRoot.find( arr ));
}
}
测试运行结果:
[6, 3, 7, 9, 3, 5, 9, 4, 5, 0, 1, 1, 2, 1, 3, 0, 1, 9, 10, 19]
target index=18
result index=17
分享到:
相关推荐
【二叉排序树与文件操作】 功能要求: (1)从键盘输入一组学生记录建立二叉排序树; (2)二叉排序树存盘; (3)由文件恢复内存的二叉排序树; (4)中序遍历二叉排序树; (5)求二叉排序树深度; (6)求二叉...
设二叉排序树的二叉链表存储结构的类型定义如下: typedef struct node{ int data; //用整数表示一个结点的名 struct node *LChild,*RChild; //左右指针域 }BSTNode,*BSTree; 设计算法并编写程序求解以下几个问题...
二叉排序树的基本操作 void insert(bstree * t,int key) {bstnode *f,*p; p=*t; while(p) {if(p->key==key)return; f=p; p=(key<p->key)?p->lchild:p->rchild; } p=(bstnode *)malloc(sizeof(bstnode...
(1)初始化二叉排序树 void InitBiTree(BiTree t) (2) 建立二叉排序树 BiTree CreateBiTree(void) (3)在二叉排序树上查找元素 BiTree SearchBST(BiTree t, int k) (4) 在二叉排序树上插入元素 BiTree InsertBST...
当二叉排序树BST中不存在结点值等于e时,插入e并返回0,否则返回-1. ③int deleteBST(BTree *T, char key);删除 若二叉排序树T中存在结点值等于key时,则删除该数据元素,并返回0;否则返回-1。 ④BTree searchBST...
建立二插排序树,首先用一个一维数组记录下读入的数据,然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置,为空的树结点用“0” 补齐。 1.2.2 建立二叉排序树 二叉排序树是一种动态树表。其特点...
#define datatype int int count; typedef struct bitnode { datatype data; struct bitnode *lchild,*rchild; }bitnode,*bitree; bitree bt=NULL; void find_number(bitree *t,datatype num) { if((*t)==NULL) ...
6. 编写一个方法search(int a[],int x): 若数组a中存在值为x 的元素,则返回该元素的下标值;否则返回-1。 7. 编写一个方法print_MaxMin(int a[]): 打印出数组a中的最大值和最小值。 8. 编写一个递归方法...
int found(Bstnode *p,int a, int b) //查找两个不同结点的最近公共祖先 { Bstnode *q; int i=0; if(a==p->key||b==p->key) return i; //如果两个结点中有一个是根结点 else while(p!=NULL){ //则表明它们没有...
cout建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "; Head=NULL; int number; cin>>number; while(number!=-1) { Head=buildTree(Head,number); cin>>number; } } template ...
2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树,并完成插入13删除关键字53和24的操作。 public static void main(String[] args) { try (Scanner sc = new Scanner(System.in)) { System.out....
1,结点的权值为int型 【输入形式】 输入n个结点,其为整数 【输出形式】 二叉排序树的中根序和后根序遍历结果 【样例输入】 6 49 37 65 21 48 86 【样例输出】 21 37 48 49 65 86 21 48 37 86 65 49
②二叉排序树插入函数 InsertNode(TREE **TREE,int key) ③二叉排序树删除函数 DeleteNode(TREE **tree,int key) (2)调用上述函数实现下列操作。 ①初始化二叉树。 ②调用插入函数建立二叉排序树。 ...
现在网上没有一个写的正确又容易让人看懂的关于把一个int类型的数组的内容放到一棵二叉树上的代码。所以,我自己写了一个。供大家学习参考。代码已经运行过了,没有任何问题。
int data; struct node* lchild,*rchild; }* BTREE; BTREE Sort_tree(int k[],int n); void Insert(BTREE & t,int item); void INORDER(BTREE &t); int main(){ int i=0,numOfInt;BTREE t; scanf("%d",&...
typedef int ElemType; typedef struct node { ElemType data; struct node *lch,*rch; }Snode; Snode *creat_bt0(); Snode *creat_bt1(); Snode *insert0(Snode *t,Snode *s); Snode *insert1(Snode *t,Snode *s)...
9.31④ 试写一个判别给定二叉树是否为二叉排序树 的算法,设此二叉树以二叉链表作存储结构。且树中 结点的关键字均不同。 9.33③ 编写递归算法,从大到小输出给定二叉排序树 中所有关键字不小于x的数据元素。要求你...
实现CreateTree函数函数原型:btnode *CreateTree (int n)形参说明:n: 节点个数返回值说明:返回树的根节点指针函数功能:构建有n个节点的二叉排序树,第一个节点为根节点,其它节点依次按照二叉排序树的构造过程...
int k; for(i=0;i;i++) { k=1+rand()0; InsertBiTree(T,k); } return true; } bool InOrderTraverse(BiTree T) { if(T==NULL) return false; if(T!=NULL) { InOrderTraverse(T->lchild); cout...
java数组 ...T[ ]:表示数组的类型 如:int[ ] 整型数组、double[ ] 浮点型数组 N:表示数组的长度 如:5表示存放5个对应类型的元素 本资源是java数组基础教程,适合自学的朋友,有兴趣可以下载学习参考。