C++刷题篇——04找等值元素

一、题目

二、解题思路

1、分割后放进二维数组

2、使用map，key为数值，value为其坐标

3、遍历二维数组元素，再在map中找该元素对应的value值（二维数组形式），倘若value.size为1，那直接返回-1，否则继续遍历value（二维数组），将值减去当前i，j坐标后不断比较取出最小值放进数组，放进的位置正好就是该元素对应的i，j位置

三、代码

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>using namespace std;vector<int>split(string params) {vector<int>p;while (params.find(" ") != string::npos) {int found = params.find(" ");p.push_back(stoi(params.substr(0, found)));params = params.substr(found + 1);}p.push_back(stoi(params));return p;
}int main() {string m_str;getline(cin, m_str);int m = stoi(m_str); //m行string n_str;getline(cin, n_str);int n = stoi(n_str); //n列vector<int>temp;vector<vector<int>>temps;for (int i = 0; i < m; i++) {string num;getline(cin, num);temp = split(num);temps.push_back(temp);temp.clear();}//key为数值，value为该值的坐标map<int, vector<vector<int>>>num_map;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {vector<int>sit;sit.push_back(i);sit.push_back(j);num_map[temps[i][j]].push_back(sit);sit.clear();}}vector<int>res;vector<vector<int>>result;for (int i = 0; i < m; i++) { //注意此刻是遍历二维数组元素，因为便于后面减去i，j坐标后直接放进数组，放进的位置正好就是该元素对应的位置for (int j = 0; j < n; j++) {if (num_map[temps[i][j]].size() == 1) { //依次遍历二维数组key，如果其对应的value仅有一个元素，返回-1res.push_back(-1);}else {int min_distance = INT_MAX; //不确定最小值比多少少，这里就先给一个最大值，最小值的写法：INT_MINfor (int k = 0; k < num_map[temps[i][j]].size(); k++) {int distance = abs(num_map[temps[i][j]][k][0] - i) + abs(num_map[temps[i][j]][k][1] - j); //当前元素坐标就为i，j，所以直接遍历坐标相减即可if (distance == 0) { //排除坐标等于自己的情况continue;}min_distance = min(min_distance, distance);}res.push_back(min_distance); //由于依次遍历i，j，所以放进的位置也是按照顺序的}}result.push_back(res); //遍历完每一行后，放进二维数组res.clear(); //及时清空一维数组}string r = "";for (auto x : result) {for (auto y : x) {r += to_string(y) + ",";}r = r.substr(0, r.size() - 1) + "],[";}r = "[[" + r.substr(0, r.size() - 2) + "]";cout << r << endl;return 0;
}