算法题：数组中出现数字个数总结

找出数组中出现次数超过一半的数字（剑指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

算法题：数组中出现数字个数总结

推荐阅读更多精彩内容