题解 | #找位置#巧妙解决输出格式问题
找位置
http://www.nowcoder.com/practice/e3b2cc44aa9b4851bdca89dd79c53150
问题分析：
这个问题难就难在如何判断当前是否是最后一个出现的，因为输出格式有要求。最后一个的输出格式跟前面的不同，
那么我们可以转换一下思路，假设每次找到重复的值，每次只输出上一次出现的位置，并用tmp保存当前位置，
那么最后一次出现的位置就不会被输出出来，然后判断tmp是否==i，不等说明重复值最后一个没有输出，然后按最
后出现位置的输出格式补上就行了。
复杂度分析：
时间复杂度O(n2)：因为每个元素都遍历了该元素后面的所有元素。
空间复杂度O(1)：只定义了几个变量。
优化思路：
因为字符串形式是确定的，那么我们可以利用map来做，只是我已经忘了map的一些基础格式和函数调用。
完全可以直接遍历一遍字符串，每次让str[i]的值作为key，保存其位置i，如果当前map里没有key就加入，否则直接在key后面加入i。
那么因为map没有改变字符出现的相对位置，只要key关键字后面的长度>=2,就说明有重复，输出就行了。
这样时间复杂度为O(n)。实在是已经忘了map的一些基础用法，只知道个大概。
这样做的空间复杂度其实也不高，最大也就是O(n)。对于字符串特别长的完全有必要这么做。
#include <string>
#include <iostream>
using namespace std;
int main() {
string str;
while(cin>>str) {
int tmp;
for(int i=0;i<str.size();++i) {
if(str[i]=='*') continue;
tmp=i;
for(int k=i+1;k<str.size();++k){
if(str[i]==str[k]) {
str[k]='*';
cout<<str[i]<<":"<<tmp<<",";//每次只输出上一个出现的位置
tmp=k;
}
}
if(tmp!=i) cout<<str[i]<<":"<<tmp<<endl;//最后补上最后一次出现的位置
}
}
}
投递金山WPS等公司10个岗位 >
拼多多集团-PDD成长空间 486人发布