【C++ LC.2089 找出数组排序后的目标下标】

/*  给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。
目标下标 是一个满足?nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。
如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。

示例：
输入：nums = [1,2,5,2,3], target = 2
输出：[1,2]

解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 2 的下标是 1 和 2 。
来源：力扣（LeetCode）  */

//法一 先排序再全部遍历一遍 
class Solution{
	public:
	vector<int> targetIndices(vector<int>& nums,int target){
		int n=nums.size();
		sort(nums.begin(),nums.end());   //从小到大排序
		vector<int> result;
		for(int i=0;i<n;i++){
			if(nums[i]==target){
				result.push_back(i);
			}
		} 
		return result;
	} 
};

//法二
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int n=nums.size();
		for(int i=0;i<n-1;i++){   //冒泡排序法，背！！！ 
			for(int j=0;j<n-1-i;j++){
                if(nums[j]>nums[j+1]){
                    int p;
				    p=nums[j];
				    nums[j]=nums[j+1];
				    nums[j+1]=p;
			    }
            }
		}      
		vector<int> result;
		for(int i=0;i<n;i++){
			if(nums[i]==target){
				result.push_back(i);
			}
		} 
		return result;
    }
}; 

//法三
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int cnt1=0;//小于target的元素的数量
		int cnt2=0;//等于target的元素的数量
		for(const int num:nums){  
			if(num<target){
				cnt1++;
			}
			if(num==target){
				cnt2++;
			}
	    }
	/*  相当于用迭代器遍历容器
	    for (vector<int>::iterator iter=nums.begin();iter!=nums.end();iter++) 
	*/		
			vector<int> result;    //输出下标数组
			for(int i=cnt1;i<cnt1+cnt2;i++){  //排序后的数组相等的值对应的下标一定是连在一起的 
				result.push_back(i);
			} 
			return result;
		} 
};