数组(5-8)

数组中只出现一次的数字

思路： 从set的角度（set中不允许出现重复元素）
步骤：

定义一个set
遍历数组，若集合中没有该元素，则将此元素加入set中，若集合中有该元素，则将集合中的该元素删除（数组中出现两次的元素）
最终集合中留下的就是只出现一次的元素

ps:找有没有是用的set的find接口，返回的是一个迭代器，若存在返回元素位置，若不存在返回s.end();往set中加入元素用的是insert接口，删除是erase接口

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        set<int> s;
        for(int i=0;i<data.size();i++)
        {
            if(s.find(data[i])==s.end())
            {
                s.insert(data[i]);
            }
            else s.erase(data[i]);
        }
        set<int>::iterator it=s.begin();
        *num1=*it;
        it++;
        *num2=*it;

    }
};

数组中重复的数字

思路：利用set的特性，set中不允许重复元素
步骤：
1.定义一个set
2.遍历数组，若set中不存在，则往里加，若存在，就返回1，这个数组元素就是第一个重复元素

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        set<int> s;
        for(int i=0;i<length;i++)
        {
            if(s.find(numbers[i])==s.end())
            {
                s.insert(numbers[i]);
            }
            else
            {
                *duplication=numbers[i];
                return 1;
            }
        }
        return 0;

    }
};

连续子数组的最大和

思路：对于第i个位置的元素来说，若它前面的sum是负数，则没有必要加上前面的sum，从当前i开始进行求和；若它前面的sum是正数，那么加上它本身
步骤：

定义一个sum（初始值可以设为a[0]）进行求和，再定义一个maxSum(初始值可以设为sum)保存最大和
i从1开始遍历，若前面的sum大于0，则sum=sum+a[i]；若前面的sum<0,则sum从a[i]重新开始

每一次循环后都要判断此时sum大于maxSum么，如果大于，就更新maxSum

class Solution {
public:
 int FindGreatestSumOfSubArray(vector<int> array) {
     int sum=array[0];
     int maxSum=sum;
     int length=array.size();
     for(int i=1;i<length;i++)
     {
         if(sum<=0)
         {
             sum=array[i];
         }
         else
             sum+=array[i];
         if(sum>maxSum)
         {
             maxSum=sum;
         }
     }
     return maxSum;

 }
};

调整数组顺序使奇数位于偶数前面

思路：定义一个奇数数组和偶数数组
步骤：
1.定义两个数组，一个存放奇数，一个存放偶数
2.遍历原数组，若元素为奇数，加入到v1；若元素为偶数，加入到v2
3.清空原数组
4.分别将v1和v2中的元素加入到原数组中去

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int>v1;
        vector<int>v2;
        for(int i=0;i<array.size();i++)
        {
            if(array[i]%2==0)
            {
                v2.push_back(array[i]);
            }
            else
                v1.push_back(array[i]);
        }
        array.clear();
        for(int i=0;i<v1.size();i++)
        {
            array.push_back(v1[i]);
        }
        for(int i=0;i<v2.size();i++)
        {
            array.push_back(v2[i]);
        }

    }
};