重庆幸运农场中奖金额|重庆幸运农场官网
MyException - 我的異常網
當前位置:我的異常網» 綜合 » 算法導論9.2以期待線性時間做選擇

算法導論9.2以期待線性時間做選擇

www.h0f1.com  網友分享于:2015-02-11  瀏覽:0次
算法導論9.2以期望線性時間做選擇

 

)M}UNMPAEY)PAYP61@BLT73

 

image

 

M1OB`15_K0U_B_GGB1(LFEA

 

#include <stdint.h>
#include <time.h>
#include <iostream>
#ifdef __linux
#include <stdio.h>
#include <stdlib.h>
#endif

void swap(int64_t* A, uint64_t i, uint64_t j)
{
    int64_t tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

int64_t partition(int64_t* A, int64_t p, int64_t r)
{
    int64_t x = A[r];
    int64_t i = p;
    for (int64_t j = p; j < r; j++)
    {
        if (A[j] <= x)
        {
            swap(A, i, j);
            i++;
        }
    }
    swap(A, i, r);
    return i;
}

int64_t RandomizedPartition(int64_t* A, int64_t p, int64_t r)
{
    int64_t i = (rand() % (r - p)) + p;
    swap(A, i, r);
    return partition(A, p, r);
}

// RANDOMIZED-SELECT(A, p, r, i)
// if p == r
//     return A[p]
// q = RANDOMIZED-PARTITION(A, p, r)
// k = q - p + 1
// if i == k
// return A[q]
// else if i < k
//     return RANDOMIZED-SELECT(A, p, q - 1, i)
// else
//     return RANDOMIZED-SELECT(A, q + 1, r, i - k)

int64_t RandomizedSelect(int64_t* A, int64_t p, int64_t r, int64_t i)
{
    if (p == r)
    {
        return A[p];
    }
    int64_t q = RandomizedPartition(A, p, r);
    int64_t k = q - p + 1;
    if (i == k)
    {
        return A[q];
    }
    else if (i < k)
    {
        return RandomizedSelect(A, p, q - 1, i);
    }
    else
    {
        return RandomizedSelect(A, q + 1, r, i - k);
    }
}
int main()
{
    int64_t array[] = { 2, 8, 7, 1, 3, 5, 6, 4 };
    
    std::cout << RandomizedSelect(array, 0, 7, 3) << std::endl;
    getchar();
    return 0;
}
BIN     = bin
FMCSA   = find_max_crossing_subarray
IAS     = IA_solution
IST     = insertion_sort_t
LMSA    = liner_time_max_subarray
MERGE   = merge
MERGE_T = merge_t
VMS     = violate_max_subarray
STRA    = 4.2_strassen
COUNT_SORT = 8.2_counting_sort
MINIMUMMAXIMUM = 9.1_MinimumMaximum
RS = 9.2_RandomizedSelect
RQ = 7.3_RandomizedQuicksort
QS = 7.1_quicksort

CFLAGS = -g -Wall

all : ${BIN}/${COUNT_SORT} ${BIN}/${RS} ${BIN}/${QS} ${BIN}/${FMCSA} ${BIN}/${RQ} ${BIN}/${IAS} ${BIN}/${IST} ${BIN}/${LMSA} ${BIN}/${MERGE} ${BIN}/${MERGE_T} ${BIN}/${VMS} ${BIN}/${STRA} ${BIN}/${MINIMUMMAXIMUM}

${BIN}/${COUNT_SORT} : ${COUNT_SORT}/counting_sort.cpp
	g++ ${COUNT_SORT}/counting_sort.cpp ${CFLAGS} -o ${BIN}/${COUNT_SORT}

${BIN}/${FMCSA} : ${FMCSA}/main.cpp ${FMCSA}/max_sub_array.h
	g++ ${FMCSA}/main.cpp ${CFLAGS} -o ${BIN}/${FMCSA}

${BIN}/${IAS} : ${IAS}/insertion_sort.cpp ${IAS}/insertion_sort.h
	g++ ${IAS}/insertion_sort.cpp ${CFLAGS} -o ${BIN}/${IAS}

${BIN}/${IST} : ${IST}/${IST}.cpp ${IST}/${IST}.h
	g++ ${IST}/${IST}.cpp ${CFLAGS} -o ${BIN}/${IST}

${BIN}/${LMSA} : ${LMSA}/Source.cpp
	g++ ${LMSA}/Source.cpp ${CFLAGS} -o ${BIN}/${LMSA}

${BIN}/${MERGE} : ${MERGE}/${MERGE}.cpp  ${MERGE}/${MERGE}.h
	g++ -std=c++0x ${MERGE}/${MERGE}.cpp ${CFLAGS} -o ${BIN}/${MERGE}

${BIN}/${MERGE_T} : ${MERGE_T}/${MERGE_T}.cpp  ${MERGE_T}/${MERGE_T}.h
	g++ -std=c++0x ${MERGE_T}/${MERGE_T}.cpp ${CFLAGS} -o ${BIN}/${MERGE_T}

${BIN}/${VMS} : ${VMS}/Source.cpp
	g++ ${VMS}/Source.cpp ${CFLAGS} -o ${BIN}/${VMS}

${BIN}/${STRA} : ${STRA}/strassen.cpp ${STRA}/strassen.h
	g++ -std=c++0x ${STRA}/strassen.cpp ${CFLAGS} -o ${BIN}/${STRA}

${BIN}/${MINIMUMMAXIMUM} : ${MINIMUMMAXIMUM}/${MINIMUMMAXIMUM}.cpp
	g++ ${MINIMUMMAXIMUM}/${MINIMUMMAXIMUM}.cpp ${CFLAGS} -o ${BIN}/${MINIMUMMAXIMUM}
	
${BIN}/${RS} : ${RS}/${RS}.cpp
	g++ ${RS}/${RS}.cpp ${CFLAGS} -o ${BIN}/${RS}

${BIN}/${RQ} : ${RQ}/${RQ}.cpp
	g++ ${RQ}/${RQ}.cpp ${CFLAGS} -o ${BIN}/${RQ}
	
${BIN}/${QS} : ${QS}/${QS}.cpp ${QS}/${QS}.h
	g++ ${QS}/${QS}.cpp ${CFLAGS} -o ${BIN}/${QS}

clean:
	rm ${BIN}/*

 

rdn_4eb5de1ea06f1

rdn_4eb5de215ff73

rdn_4eb5de22051f3

文章評論

團隊中“技術大拿”并非越多越好
團隊中“技術大拿”并非越多越好
初級 vs 高級開發者 哪個性價比更高?
初級 vs 高級開發者 哪個性價比更高?
60個開發者不容錯過的免費資源庫
60個開發者不容錯過的免費資源庫
程序員都該閱讀的書
程序員都該閱讀的書
2013年美國開發者薪資調查報告
2013年美國開發者薪資調查報告
十大編程算法助程序員走上高手之路
十大編程算法助程序員走上高手之路
編程語言是女人
編程語言是女人
要嫁就嫁程序猿—錢多話少死的早
要嫁就嫁程序猿—錢多話少死的早
Java 與 .NET 的平臺發展之爭
Java 與 .NET 的平臺發展之爭
每天工作4小時的程序員
每天工作4小時的程序員
漫畫:程序員的工作
漫畫:程序員的工作
中美印日四國程序員比較
中美印日四國程序員比較
“懶”出效率是程序員的美德
“懶”出效率是程序員的美德
程序員的一天:一寸光陰一寸金
程序員的一天:一寸光陰一寸金
我是如何打敗拖延癥的
我是如何打敗拖延癥的
為什么程序員都是夜貓子
為什么程序員都是夜貓子
不懂技術不要對懂技術的人說這很容易實現
不懂技術不要對懂技術的人說這很容易實現
那些性感的讓人尖叫的程序員
那些性感的讓人尖叫的程序員
2013年中國軟件開發者薪資調查報告
2013年中國軟件開發者薪資調查報告
Web開發人員為什么越來越懶了?
Web開發人員為什么越來越懶了?
總結2014中國互聯網十大段子
總結2014中國互聯網十大段子
“骯臟的”IT工作排行榜
“骯臟的”IT工作排行榜
我跳槽是因為他們的顯示器更大
我跳槽是因為他們的顯示器更大
我的丈夫是個程序員
我的丈夫是個程序員
程序員必看的十大電影
程序員必看的十大電影
老程序員的下場
老程序員的下場
程序員眼里IE瀏覽器是什么樣的
程序員眼里IE瀏覽器是什么樣的
10個調試和排錯的小建議
10個調試和排錯的小建議
如何成為一名黑客
如何成為一名黑客
鮮為人知的編程真相
鮮為人知的編程真相
10個幫程序員減壓放松的網站
10個幫程序員減壓放松的網站
什么才是優秀的用戶界面設計
什么才是優秀的用戶界面設計
那些爭議最大的編程觀點
那些爭議最大的編程觀點
Java程序員必看電影
Java程序員必看電影
Web開發者需具備的8個好習慣
Web開發者需具備的8個好習慣
程序員應該關注的一些事兒
程序員應該關注的一些事兒
一個程序員的時間管理
一個程序員的時間管理
程序員的鄙視鏈
程序員的鄙視鏈
程序員最害怕的5件事 你中招了嗎?
程序員最害怕的5件事 你中招了嗎?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
親愛的項目經理,我恨你
親愛的項目經理,我恨你
如何區分一個程序員是“老手“還是“新手“?
如何區分一個程序員是“老手“還是“新手“?
看13位CEO、創始人和高管如何提高工作效率
看13位CEO、創始人和高管如何提高工作效率
做程序猿的老婆應該注意的一些事情
做程序猿的老婆應該注意的一些事情
旅行,寫作,編程
旅行,寫作,編程
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
代碼女神橫空出世
代碼女神橫空出世
Google倫敦新總部 猶如星級莊園
Google倫敦新總部 猶如星級莊園
軟件開發程序錯誤異常ExceptionCopyright © 2009-2015 MyException 版權所有
重庆幸运农场中奖金额 重庆时时彩-安卓版 11选五5技巧稳赚 二码三肖100% 足球单场结果 3d组六8码多少钱 重庆时时历史开奖号码 三地五码全组最大遗漏 重庆欢乐生肖彩票走势图 重庆时时彩的qq群 重庆时时彩5码个位技巧 11选5大小单双投注方法 北京pk赛车一分钟计划 炸金花手法和技巧 黑龙江时时暂停 大乐透小助手下载安装 广东时时几点开盘