c++ - 向量上的线性搜索
问题描述
我有测试可以使用我创建的方法在线通过。我感觉其中一项测试有问题。最后一个我不能通过。这是测试-
TEST_CASE ("Linear Search With Self-Organization 3") {
int searchKey = 191;
vector<int> searchArray(500);
for (int i = 0; i < 500; i++) {
searchArray[i] = i + 1;
}
random_shuffle(searchArray.begin(), searchArray.end());
bool result, result2;
result = linearSearchSO(searchArray, searchKey);
int searchKey2 = 243;
result2 = linearSearchSO(searchArray, searchKey2);
REQUIRE (result == true);
REQUIRE (result2 == true);
REQUIRE (verifySearchArray(searchArray) == true);
REQUIRE (searchArray[0] == searchKey2);
REQUIRE (searchArray[1] == searchKey);
REQUIRE (searchArray.size() == 500);
}
这里讨论的方法是linearSearchSO。
bool linearSearchSO(vector<int> & inputArr, int searchKey) {
printArray(inputArr);
for(int i=0; i < inputArr.size(); i++) {
int temp = inputArr[0];
if (inputArr[i] == searchKey) {
inputArr[0] = inputArr[i];
inputArr[i] = temp;
printArray(inputArr);
return true;
}
}
return false;
}
值得注意的是,此方法已通过所需的所有其他 3 项测试。正如您在测试中看到的那样,我的导师两次调用此方法并传递两个不同的值。想法是有一个由 500 个数字组成的向量。在这种情况下,他将数字随机化。对我来说,解释正在发生的事情的最好方法是,如果他没有随机化并且数字只是列出了 1-500。该方法被调用,我从请求的数字 191 开始,我将它移动到向量的前面。现在它读取 191、2、3、4 等。190、1、192 等。于是他再次调用该方法,并希望将 243 移到前面。他的测试希望结果为 243、191、2、3、4。但是我的代码所做的是将 191 交换到 243 的位置。我的结果现在显示为 243、2、3、4 等。242、191、244、245 等。
其他所有测试都只是简单地将一个数字移到前面,然后测试检查每个数字是否在正确的位置。我的问题是,有没有办法让我达到 243、191、2、3.. 而不会弄乱我只使用这个线性搜索功能通过的所有其他测试?或者是测试有问题,他只是犯了一个错误。
编辑-这个测试的实际问题。问题 4 自组织搜索算法是一种重新排列集合中的项目,以便在搜索中更快地找到那些经常搜索的项目。修改线性搜索的学习算法,使得每次在数组中找到一个项目时,该项目与数组开头的项目交换。
解决方案
如果我理解正确,您需要以下内容
#include <iostream>
#include <vector>
bool linearSearchSO( std::vector<int> & inputArr, int searchKey )
{
bool success = false;
auto it = inputArr.begin();
while ( it != inputArr.end() && *it != searchKey ) ++it;
if ( ( success = it != inputArr.end() ) )
{
int value = *it;
inputArr.erase( it );
inputArr.insert( inputArr.begin(), value );
}
return success;
}
int main()
{
std::vector<int> inputArr = { 1, 2, 3, 4, 5 };
for ( const auto &item : inputArr )
{
std::cout << item << ' ';
}
std::cout << '\n';
linearSearchSO( inputArr, 3 );
for ( const auto &item : inputArr )
{
std::cout << item << ' ';
}
std::cout << '\n';
}
程序输出为
1 2 3 4 5
3 1 2 4 5
请注意,您可以使用标准算法,而不是在函数中手动编写循环std::find
。
推荐阅读
- php - 从父行到子行的数组模式
- youtube-api - 如何获取 youtube 视频的哈希值?
- python - ValueError:未能找到可以处理输入的数据适配器:
, ( 包含类型 {" "}) - python - 在 GCP 上部署的 Flask 应用程序出现内部服务器错误
- ios - 如何处理 WKWebView 中缺少 http:// 或 https:// 的网址?
- rasa-nlu - Rasa AttributeError:“NoneType”对象没有属性“startswith”
- html - 为什么“无”出现在 Django cms 的导航栏和正文之间
- mysql - 如何恢复frm和ibd文件?
- heroku - 可以在heroku上设置NATS协议吗?
- java - 尝试从 testng.xml 运行我的测试时出现 NullPointerException