請(qǐng)教一個(gè)C++的數(shù)字和字符混合排序的算法。
輸入是一個(gè)string array,所有元素本質(zhì)上都是string,比如 [2, Banana, 1, Apple, 3, Pear]?,F(xiàn)在給它排序,要求排序之后的輸出是 [1, Apple, 2, Banana, 3, Pear]??傊褪菙?shù)字與數(shù)字排序,字符與字符排序,原來(lái)是string的位置放string,是integer的位置放integer(話說(shuō)回來(lái),其實(shí)所有元素本質(zhì)上都是string,只不過有些是數(shù)字形式而已)。
我覺得必須要實(shí)現(xiàn)一下判斷字符串是否是數(shù)字。C++應(yīng)該直接可以用::isdigit吧?但是請(qǐng)問一下,應(yīng)該怎么實(shí)現(xiàn)原來(lái)是string的位置放string、是integer的位置放integer呢?
也許可以用堆排序來(lái)實(shí)現(xiàn)這個(gè)算法。所以另外再請(qǐng)教一個(gè)最小堆priority_queue的定義問題。
struct cmp
{
bool operator () (int a, int b)
{ return a>b; }
};
void heaping1()
{
priority_queue<int, vector<int>, cmp> pq;
這樣定義priority_queue是可以通過編譯的。但是,如果改為以下定義:
void heaping2()
{
priority_queue<pair<int, char>, cmp> pq;
這樣定義priority_queue就無(wú)法通過編譯了!當(dāng)然,如果刪除了cmp改為最大堆,那么一切正常。所以,請(qǐng)問上面函數(shù)中的最小堆應(yīng)該如何定義呢?cmp應(yīng)該放在哪里呢?謝謝了先!
不用 inplace (直接分成兩個(gè)數(shù)組排序,再合并) 的話就太簡(jiǎn)單了,要 inplace 的話其實(shí)也可以不用手寫 iterator,手寫一個(gè) reference 的 wrapper 就行了(然后直接調(diào)用任意 常規(guī) inplace 排序算法即可):
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
template <typename T>
class Ref {
T & t;
public:
Ref(T & t) : t(t) {
}
Ref(Ref & o) : t(o.t) {
}
Ref(Ref && o) : t(o.t) {
}
Ref & operator = (Ref & o) {
t = o.t;
return *this;
}
Ref & operator = (Ref && o) {
t = move(o.t);
return *this;
}
bool operator < (Ref const & o) const {
return t < o.t;
}
friend void swap(Ref & a, Ref & b) {
using std::swap;
swap(a.t, b.t);
}
};
void solution(vector<string> & ret) {
vector<Ref<string>> a;
vector<Ref<string>> b;
for (auto & c : ret) {
bool numeric = true;
for (auto const & d : c) {
if (!isdigit(d)) numeric = false;
}
if (numeric) a.emplace_back(c); else b.emplace_back(c);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<string> v;
string l;
getline(cin, l);
stringstream ss;
ss << l;
string s;
while (ss >> s) {
v.emplace_back(move(s));
}
solution(v);
bool first = true;
for (auto const & c : v) {
if (first) first = false; else cout.put(' ');
cout << c;
}
cout << '\n';
}
測(cè)試:
輸入
2 Banana 1 Apple 3 Pear
輸出
1 Apple 2 Banana 3 Pear
這道題主要思路是要用原址排序,例如快排,
我這里實(shí)現(xiàn)了自定義的迭代器,然后用std::sort排序,你也可以自己實(shí)現(xiàn)快排,當(dāng)然可能更簡(jiǎn)單一些,不過要小心邊界。
#include <iterator>
#include <iostream>
#include <cctype>
#include <algorithm>
bool sortNum = true;
bool isNum(const char* num)
{
while (*num)
{
if (!std::isdigit(*num))
return false;
++num;
}
return true;
}
class Myiter :public std::iterator<std::random_access_iterator_tag,const char *>
{
const char** ptrStr_= nullptr;
const char** end_ = nullptr;
const char** begin_ = nullptr;
public:
explicit Myiter(const char** ptr=nullptr):ptrStr_(ptr) {}
Myiter(const Myiter& that) :ptrStr_(that.ptrStr_),end_(that.end_) {}
Myiter& setEnd(const char** end) { end_ = end; return *this; }
Myiter& setBegin(const char** begin) { begin_ = begin; return *this; }
Myiter& operator++()
{
++ptrStr_;
while ( ptrStr_!= end_)
{
auto str = *ptrStr_;
if (sortNum)
{
if (isNum(*ptrStr_))
return *this;
}
else
{
if (!isNum(*ptrStr_))
return *this;
}
++ptrStr_;
}
return *this;
}
Myiter operator++(int)
{
Myiter tmp(*this);
++tmp;
return tmp;
}
Myiter& operator+=(difference_type n)
{
while (--n != 0)
++*this;
return *this;
}
Myiter operator+(difference_type n)
{
Myiter tmp(*this);
tmp += n;
return tmp;
}
Myiter& operator--()
{
while (--ptrStr_!=begin_)
{
auto str = *ptrStr_;
if (sortNum)
{
if (isNum(*ptrStr_))
return *this;
}
else
{
if (!isNum(*ptrStr_))
return *this;
}
}
return *this;
}
Myiter operator--(int)
{
Myiter tmp(*this);
--tmp;
return tmp;
}
Myiter& operator-=(difference_type n)
{
while (--n != 0)
--*this;
return *this;
}
Myiter operator-(difference_type n)
{
Myiter tmp(*this);
tmp -= n;
return tmp;
}
reference operator*() const { return *ptrStr_; }
bool operator!=(const Myiter& that) { return ptrStr_ != that.ptrStr_; }
bool operator==(const Myiter& that) { return ptrStr_ == that.ptrStr_; }
bool operator<(const Myiter& that) { return ptrStr_ < that.ptrStr_; }
bool operator>(const Myiter& that) { return ptrStr_ > that.ptrStr_; }
bool operator<=(const Myiter& that) { return ptrStr_ <= that.ptrStr_; }
bool operator>=(const Myiter& that) { return ptrStr_ >= that.ptrStr_; }
difference_type operator-(const Myiter& that)
{
Myiter tmp(that);
difference_type n = 0;
while ((*this)!= tmp)
{
++n;
++tmp;
}
return n;
}
};
template<size_t N>
void sortAndPrint(const char* (&test)[N] )
{
std::cout << "Before sort:\n";
for (auto i : test)
{
std::cout << i << " ";
}
std::cout << "\n";
auto size = N;
auto end = test + size;
auto begin = test;
auto startNum = test;
auto startStr = test;
bool gotStartNum = false;
bool gotStartStr = false;
for (; begin != end; ++begin)
{
if (gotStartNum&&gotStartStr) break;
if (isNum(*begin))
{
if (gotStartNum) continue;
startNum = begin;
gotStartNum = true;
}
else
{
if (gotStartStr) continue;
startStr = begin;
gotStartStr = true;
}
}
sortNum = true;
std::sort(Myiter(startNum).setBegin(startNum).setEnd(end), Myiter(end).setBegin(startNum).setEnd(end), [](const char* a, const char *b)
{
auto aNum = atoi(a);
auto bNum = atoi(b);
return aNum < bNum;
});
sortNum = false;
std::sort(Myiter(startStr).setBegin(startStr).setEnd(end), Myiter(end).setBegin(startStr).setEnd(end), [](const char* a, const char *b)
{
return strcmp(a, b) < 0;
});
std::cout << "After sort:\n";
for (auto i : test)
{
std::cout << i << " ";
}
std::cout << "\n";
}
int main()
{
const char * test[] = { "3","1","Charlie","Alpha","Bravo" };
const char * test2[] = { "2", "Banana", "1", "Apple", "3", "Pear" };
sortAndPrint(test);
sortAndPrint(test2);
system("PAUSE");
}
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國(guó)IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國(guó)家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團(tuán)創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機(jī)構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團(tuán),成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達(dá)內(nèi)教育集團(tuán)成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機(jī)構(gòu),是中國(guó)一站式人才培養(yǎng)平臺(tái)、一站式人才輸送平臺(tái)。2014年4月3日在美國(guó)成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項(xiàng)目經(jīng)理從事移動(dòng)互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍(lán)懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負(fù)責(zé)iOS教學(xué)及管理工作。
浪潮集團(tuán)項(xiàng)目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺(tái)面向?qū)ο箝_發(fā)經(jīng)驗(yàn),技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點(diǎn)難點(diǎn)突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫(kù),具有快速界面開發(fā)的能力,對(duì)瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁(yè)制作和網(wǎng)頁(yè)游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗(yàn)。曾經(jīng)歷任德國(guó)Software AG 技術(shù)顧問,美國(guó)Dachieve 系統(tǒng)架構(gòu)師,美國(guó)AngelEngineers Inc. 系統(tǒng)架構(gòu)師。