- 找出数组中出现次数超过一半的数字（剑指offer29 leetcode169）
思路：1）partition，快排的部分功能，O(n)。出现次数超过一半即可用快排的思想求中位数即可。
2）根据数组的特点出发，保存一个数和一个次数，如果下次遇到的数与保存的数相同，次数加一，不同减一，次数为0 则保存下一个数，并把次数设为1.
class Solution {
public:
int majorityElement(vector<int>& nums) {
int num,count=0;
for(int i=0;i<nums.size();i++){
if(count==0)
num=nums[i];
if(nums[i]==num)
count++;
else
count--;
}
return num;
}
};
- 找出最小的k个数（topK）
1.将输入内容进行完全排序，选出排在前k的元素，可选择快速排序，堆排序和归并排序，时间复杂度O(nlogn)。
2.只对前K大的元素进行排序，可选择冒泡排序或选择排序进行处理，即每次冒泡都能找到所求的一个元素，时间复杂度O(Kn)。
3.对输入内容不进行排序：1）利用最小堆维护大小为K的数组，该小根堆中的元素是排名前K的数，其中根是最小的数。此后，每次从原数组中取一个元素与根进行比较，如大于根的元素，则将根元素替换并进行堆调整（下沉），即保证小根堆中的元素仍然是排名前K的数，且根元素仍然最小；否则不予处理，取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK)。特点：不需要一次将原数组中的内容全部加载到内存中。2）利用快排的分划函数找到划分位置k，时间复杂度O(n)。（只有当我们可以修改输入的数组时可用）
- 第一个只出现一次的字符（剑指offer35，leetcode387）
思路：1）排序，O(nlogn)
2）哈希表，第一遍扫描，用哈希表存储字符出现的个数；第二遍扫描，找出第一个个数为1的字符，O(n)
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> map;
for(int i=0;i<s.size();i++){
map[s[i]]+=1;
}
for(int i=0;i<s.size();i++){
if(map[s[i]]==1)
return i;
}
return -1;
}
};
- 字符流中第一个不重复的字符（剑指offer269，[nowcoder]
思路同上，如需存储位置，则将map中的value替换为位置，出现两次及以上赋值为-2，初始化为-1.
(https://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720)）
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
s+=ch;
map[ch]+=1;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
for(int i=0;i<s.size();i++){
if(map[s[i]]==1)
return s[i];
}
return '#';
}
unordered_map<char,int> map;
string s="";
};
- 整数数组中，第一个没有出现的正整数leetcode41
思路：考虑整数的范围和数组的长度n的关系，第一个没有出现的正整数肯定小于等于长度。
(交换可用algorithm.h里的swap)
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
if(n==0) return 1;
for(int i=0;i<n;){
if(nums[i]<n+1&&nums[i]>0&&nums[i]!=nums[nums[i]-1]){
int tmp=nums[i];
nums[i]=nums[tmp-1];
nums[tmp-1]=tmp;
}
else
i++;
}
for(int i=0;i<n;i++){
if(nums[i]!=i+1)
return i+1;
}
return n+1;
}
};
- 找出数组中只出现一次的数字，其它数字都出现了两次
异或
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result=0;
for(int i=0;i<nums.size();i++){
result=result^nums[i];
}
return result;
}
};
- 找出数组中只出现一次的数字，其它数字都出现了三次。
思路：1）使用map，增加了空间复杂度O(n)。2）排序，时间复杂度O(nlogn)
3）位操作思想，不管非孤异元素重复多少次，这是通用做法。
对于右数第i位，如果孤异元素该位为0，则该位为1的元素总数为3的整数倍。
如果孤异元素该位为1，则该位为1的元素总数不为3的整数倍（也就是余1）。
换句话说，如果第i位为1的元素总数不为3的整数倍，则孤异数的第i位为1，否则为0.
（如果非孤异元素重复n次，则判断是否为n的整数倍）
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n=nums.size();
int result=0;
for(int i=0;i<32;i++){
int count=0;
int mask=1<<i;
for(int j=0;j<n;j++){
if(nums[j]&mask)
count++;
}
if(count%3)
result|=mask;
}
return result;
}
};
http://blog.csdn.net/jeanphorn/article/details/46501331
网友评论