[数据结构与算法]Leetcode数据结构基础1

题目一链接

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //位运算  异或运算
        int ret = 0;
        for(auto e:nums) ret^=e;
        return ret;
    }
};

题目二链接

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于?? n/2 ??的元素。可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
       //将数组排序，因为 众数>nums.size()/2
       /* sort(nums.begin(),nums.end());
        return nums[nums.size()/2];*/
        
        //map 键对应元素  值为次数  利用打擂台的方式选出次数出现最多的
       /*map<int,int> map_num;
        int max_key=0,max_value=0;
        for(int num:nums)
        {
            ++map_num[num];
            if(map_num[num]>max_value)
            {
                max_value=map_num[num];
                max_key=num;
            }
        }
        return max_key;*/
        
        //摩尔投票法
       /* int count=0,num=nums[0];
        for(int num_1:nums){
            if(num_1==num){
                count++;
            }else if(--count<0){
                num=num_1;
                count=1;
            }
        }
        return num;*/
    }


};

给你一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，使得?a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

题三

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
         vector<vector<int>> v;
         if(nums.size()<3)
         return v;

         sort(nums.begin(),nums.end());//先排序

        /*if(nums[0]>0||nums[nums.size()-1]<0)
         return v;*/

         int i=0,left,right;
         while(i<nums.size()){
             if(nums[i]>0) return v;

             left=i+1;
             right=nums.size()-1;

             while(left<right){
                 if(nums[i]+nums[left]+nums[right]<0){
                     left++;
                 }else if(nums[i]+nums[left]+nums[right]>0){
                     right--;
                 }else{
                     v.push_back({nums[i],nums[left],nums[right]});
                     while(left<right&&nums[left]==nums[left+1])
                        left++;
                    while(left<right&&nums[right]==nums[right-1])
                        right--;
                    left++;
                    right--;
                 }
             }

             while(i+1<nums.size()&&nums[i]==nums[i+1])
                i++;
            i++;
         }
         return v;
    }
};