调整数组顺序

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变

https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

奇数在前偶数在后&&相对顺序可以改变的情况:

方法1:遍历两次数组,第一次遍历遇到奇数的先放到数组中,第二次遍历遇到偶数的放到数组中

方法2:头尾指针 , 头指针找偶数,尾指针找奇数,找到之后,二者交换

然后这里是奇数在前偶数在后&&相对顺序不变的情况:

利用插入排序的思想:

k前面的元素不需要再后移了,所以挪动的元素区间是(k,i],把前面的挪到后面去,从后往前挪

a[i]&1 == 0 ->偶数

a[i]&1 == 1 ->奇数

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int k = 0;//标志应该存放奇数的位置
        //遍历数组,
        //i位置遇到奇数:用临时遍历tmp保存当前位置的值
        //就把[k,i-1)的元素往后移动,然后把tmp放到k位置下
        //然后k++标志下一个应该存放奇数的位置
        for(int i = 0;i<array.size();i++)
        {
            if(array[i] & 1)
            {
                //此时i位置为奇数,即i-1下标的元素为偶数
                int tmp = array[i];//先保存当前位置的奇数
                int j = i;
                //把(k,i-1]的元素往后移动
                //k位置应该是我们放奇数的位置,所以该位置不需要往后移动
                for(int j = i;j>k;j--)
                {
                    array[j] = array[j-1];
                }
                array[k++] = tmp;
            }
        }
    }
};

数组出现超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.如果不存在则输出0.

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

因为有可能并不存在出现次数超过一半的数字,所以我们最后找到之后还需要再次遍历数组判断是否符合要求

方法1:定义map <数字,次数>的映射关系,最后统计每个数字出现的次数

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int,int> map;
        int half = numbers.size()/2;
        for(int i = 0;i<numbers.size();i++)
        {
            auto it = map.find(numbers[i]);//在map中查找是否右numbers[i]
            //如果有,则自增,没有,则在map中插入该元素,首次出现
            if(it!=map.end())
            {
                map[numbers[i]]++;
            }
            else
            {
                map.insert(make_pair(numbers[i],1)) ;   
            }
            
            //判断该元素的出现次数是否超过一半
            if(map[numbers[i]]>half)
            {
                return numbers[i];
            }
        }
        //找不到
        return -1;
    }
};

方法2:排序,出现次数最多的数字,一定在中间位置,然后再次遍历数组,检测中间出现的数字是否符合要求

class Solution {
    public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(),numbers.end());//对数组进行排序
        int ans = numbers[numbers.size()/2];//中间位置
        //判断是否符合条件
        int sum  =0;
        for(int i = 0;i<numbers.size();i++)
        {
            if(numbers[i] == ans)
            {
                sum++;
            }
        }
        //出现次数一定要>numbers.size()/2  不可以等于,因为超过一半
        if(sum>numbers.size()/2)
        {
            return ans;
        }
        //并没有超过一半,即不存在超过一半的数字
        return 0;
    }
};

方法3:抵消的思想

目标条件:目标数据超过数组长度的一半.

那么对数组,我们同时去掉两个不同的数字,到最后剩下的一个数就是该数字.如果剩下两个,那么这两个也是一样的,就是结果）,将数组遍历一遍统计一下数字出现次数进行最终判断.

class Solution {
    public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int ans = 0;
        int count = 0;//ans出现的次数
        for(int i =0;i<numbers.size();i++)
        {
            if(count == 0)
            {
                ans = numbers[i];
                count=1;//注意要把count置为1
            }
            else if(ans == numbers[i])
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        //判断是否符合条件
        int sum  =0;
        for(int i = 0;i<numbers.size();i++)
        {
            if(numbers[i] == ans)
            {
                sum++;
            }
        }
        //出现次数一定要>numbers.size()/2  不可以等于,因为超过一半
        if(sum>numbers.size()/2)
        {
            return ans;
        }
        //并没有超过一半,即不存在超过一半的数字
        return 0;
    }
};