今天莫名其妙睡到了中午，很难受。。。
leetcode442 https://leetcode.com/problems/find-all-duplicates-in-an-array/?tab=Description
leetcode531 https://leetcode.com/problems/lonely-pixel-i/?tab=Description
leetcode533 https://leetcode.com/problems/lonely-pixel-ii/?tab=Description
============================================================
442说的是
给你n个数，1 ≤ a[i] ≤ n，数组中每个数字保证只出现一次或者两次，要求输出所有出现两次的数字，空间复杂度O(0)，时间复杂度O(n)
我的思路
额。。。。因为出现的最大的数字是n，我们用每个元素的（n+1）的倍数来标记出现的次数好了。。。具体看程序
1 class Solution { 2 public: 3 vector<int> findDuplicates(vector<int>& nums) { 4 int n=nums.size(); 5 for(int i=0;i<n;i++){ 6 int temp=nums[i]%(n+1); 7 nums[temp-1]+=(n+1); 8 } 9 vector<int> aim; 10 for(int i=0;i<n;i++){ 11 int temp=nums[i]/(n+1); 12 if(temp==2)aim.push_back(i+1); 13 } 14 return aim; 15 } 16 };
但是不太好啊，一方面是可能爆上限（但是因为给的是数组，1e9其实也不太可能），另一方面是大量的使用了除法和取余，效率很低啊....
关于取负数的方法我想过，但是我认为如果出现两次，负负得正，无法和没有出现过的数字区分开，当我看了讨论版的时候我傻了。。。。谁说非要离线检查状态了，可以在线嘛，如果发现想要把一个已经是负数的数取负，直接加到答案里就是了。。。
1 public class Solution { 2 // when find a number i, flip the number at position i-1 to negative. 3 // if the number at position i-1 is already negative, i is the number that occurs twice. 4 5 public List<Integer> findDuplicates(int[] nums) { 6 List<Integer> res = new ArrayList<>(); 7 for (int i = 0; i < nums.length; ++i) { 8 int index = Math.abs(nums[i])-1; 9 if (nums[index] < 0) 10 res.add(Math.abs(index+1)); 11 nums[index] = -nums[index]; 12 } 13 return res; 14 } 15 }
然后又看到了一个骨骼惊奇的解法，因为n个数字，每个数字又保证不大于n，那么下标和数字可以对应起来，把他们放回原处，然后扫一遍，虽然感觉复杂度不是O(n)，而且正确性没有证明，不过思路倒是很独特。。
1 class Solution { 2 public: 3 vector<int> findDuplicates(vector<int>& nums) { 4 vector<int> res; 5 int i = 0; 6 while (i < nums.size()) { 7 if (nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]); 8 else i++; 9 } 10 for (i = 0; i < nums.size(); i++) { 11 if (nums[i] != i + 1) res.push_back(nums[i]); 12 } 13 return res; 14 } 15 };
=============================================================、
531说的是
给你一个二维字符数组，里面有‘W’和‘B’，问你有多少个‘B’，他的同行同列没有其他的‘B’
我的思路
这题目没什么难的，开两个数组，扫一遍记录每行每列有几个B，只有一个的话就记录坐标，多个就是-2，没有是-1，复杂度是O(n*m)，空间是O(n+m)
1 class Solution { 2 public: 3 int findLonelyPixel(vector<vector<char> >& picture) { 4 int n=picture.size(),m=picture[0].size(); 5 vector<int> cul,row; 6 for(int i=0;i<m;i++){ 7 cul.push_back(-1); 8 } 9 for(int i=0;i<n;i++){ 10 row.push_back(-1); 11 } 12 for(int i=0;i<n;i++){ 13 for(int j=0;j<m;j++){ 14 if(picture[i][j]==‘B‘){ 15 if(row[i]==-1){ 16 row[i]=j; 17 }else row[i]=-2; 18 if(cul[j]==-1){ 19 cul[j]=i; 20 }else cul[j]=-2; 21 } 22 } 23 } 24 int ans=0; 25 for(int i=0;i<n;i++) 26 if(row[i]>-1) 27 if(cul[row[i]]==i) 28 ans++; 29 return ans; 30 } 31 };
142ms超过了100%的用户hhhhhh
================================================================
原文：http://www.cnblogs.com/xuwangzihao/p/6509371.html
