日拱一卒，月进一步（8）

136. 只出现一次的数字 - 力扣（LeetCode）

这个题目一出现，我就立马有了思路。其实就是让每个数字互相异或，最后得出的数字就是只出现一次的数字。

代码语言：javascript复制

int singleNumber(int* nums, int numsSize) {
  int n=nums[0];
  for(int i=1;i<numsSize;i  )
  {
    n^=nums[i];
  }  
  return n;
}

169. 多数元素 - 力扣（LeetCode）

最初的一个想法如下，但是一定还有更简便的方法：

代码语言：javascript复制

int majorityElement(int* nums, int numsSize)
{
    for(int i=0;i<numsSize;i  )
    {
        int count=0;
        for(int j=0;j<numsSize;j  )
        {
        if(nums[i]==nums[j])
        {
            count  ;
        }
        if(count>numsSize/2)
        {
          return nums[i];
        }
    }
    }
    return -1;
}

在浏览力扣解题区的时候，果不其然发现了更加简便的方法：

投票算法可以省略循环中不必要的比较，那么我们就开始学习这是如何完成的吧。

代码语言：javascript复制

int majorityElement(int* nums, int numsSize)
{
    int candidate=nums[0];//投票对象
    int count=1;
    for(int i=0;i<numsSize;i  )//遍历投票对象
    {
        if(nums[i]==candidate)//投票对象相同，票数 1
        {
             count  ;
        }
        else//投票对象不同，票数-1
        {
            count--;
            if(count<0)//该元素不是多数元素，更新投票对象并把票数置为1
            {
                 candidate=nums[i];
                 count=1;
            }
        }
    }
    return candidate;

}

遍历 对象 算法 count int

0 人点赞