LC数组题目分类详解

• leetcode 169 求众数
  • 下面代码给出： 哈希法/排序法/投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /*//排序：中间元素
        sort(nums.begin(),nums.end());        
        return nums[nums.size()/2];
        */
        /*//哈希表
        map<int,int> mp;
        for(int i=0;i<nums.size();i++)
            mp[nums[i]]=0;
        for(int i=0;i<nums.size();i++)
        {
            mp[nums[i]]++;
            if(mp[nums[i]]>nums.size()/2)
                return nums[i];
        }
        return -1;
        */
        //投票法：相同计数器加1，不相同计数器减1，最终剩下的数为众数
        int count=0;
        int n;
        for(int i=0;i<nums.size();i++)
        {   // 背诵理解
            if(count==0)
                n=nums[i];
            count+=(n==nums[i])?1:-1;
        }
        return n;
        
    }

哈希法：用map统计个数，直接计算即可
排序法：相当于是排序之后，nums[n/2] 就是众数，这个是基于众数大于n/2的数量在数组中左右移动时肯定会占据n/2这个位置的原理。
投票法：我自己理解就是，首先众数个数是大于n/2的，极端情况是在之前，每个众数都与自己不相同的数进行投票抵消掉，但是最后还是会剩下一个众数。极端情况满足，其他肯定也满足。

• 打印实心菱形

//打印菱形：

        for (int i = 1; i <= 5; i++) {//打印上半部分空格
            for (int j = 1; j <= 5 - i; j++) {
                System.out.print(" ");
            }
            for (int j = 1; j <= 2 * i - 1; j++) {//打印上半部分*
                System.out.print("*");
            }
            System.out.println();
        }
        for (int i = 4; i >= 1; i--) {
            for (int j = 1; j <= 5 - i; j++) {
                System.out.print(" ");
            }
            for (int j = 1; j <= 2 * i - 1; j++) {
                System.out.print("*");
            }
            System.out.println();
        }
        System.out.println("-----------------");
}

• Remove Element

• Remove Duplicates from Sorted Array

• leetcode 274 H-Index
  参考2

参考
1 LeetCode:287 Find the Duplicate Number 寻找重复数
2 H-Index