首页 > 代码库 > The-ith-Element
The-ith-Element
Brief: the-ith-element,given a array A with n element , return the i-th element of A. A(n,i)
this problem can be solved using quick-sort idear, every time we choose a pivot ,after rearrangement, we know the pivot is the i-th element of A, so we can fixed this problem as the follow action.
i) choose pivot, rearrangement array, get the pivot index of j;
ii) if j > i , then recursion the 1-th partition , A(1-th , i);
iii)if j < i, then recursion the 2-th partition, A(2-th, i-j);
int element(int *array, int left, int right, int index){ if(left >= right) return array[left]; int pivot = array[left]; int i=0, j = 0; for(i=left+1,j = left+1; j <=right; ++j) { if(array[j] < pivot) swap(array[i++], array[j]); } swap(array[left], array[i-1]); //pivot is the (i-left)-th element, and pivot‘s index is i-1 if(index == i-left) return array[i-1]; else if(index < i-left) return element(array, left, i-2, index); else return element(array, i,right, index-i+left);}
The-ith-Element
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。