K 작은 수치 쌍 (정렬 구 해 O (N * logN), BFPRT 구 해 O (N)))

길이 가 N 인 배열 arr 는 반드시 N ^ 2 개의 수 치 를 구성 할 수 있 습 니 다. 예 를 들 어 arr = [3, 1, 2], 수 치 는 (3, 3) (3, 1) (1, 3) (1, 1) (1, 2) (2, 3) (2, 1) (2, 2), 즉 임 의 두 숫자 가 모두 수치 가 맞 고 자신 과 자신 도 수치 가 맞 는 정렬 규칙 을 계산 할 수 있 습 니 다. 1 차원 데 이 터 는 작은 것 에서 큰 것 으로 1 차원 데이터 와 같 습 니 다.2 차원 데이터 도 작은 것 에서 큰 것 까지 의 수치 대 정렬 결 과 는 (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 2) (3, 3) (3, 3) 주어진 배열 arr 와 정수 k 로 k 작은 수치 대 를 되 돌려 줍 니 다.
복잡 도 O (N * logN) 의 해법

/*   ：       ，
                  ，
                         
                  
*/

#include 
#include 
#include 
using namespace std;

//        O(N*logN)
vector<int> getPairKth(vector<int>& arr, int k) {
     
	if (arr.empty() || arr.size() * arr.size() <= k || k < 0) {
     
		return vector<int>();
	}
	//          O(N*logN)
	sort(arr.begin(), arr.end());
	// pair    
	int firstDim = k / arr.size();

	//                        
	int lessFirst = 0;
	int equalFirst = 0;
	for (int i = 0; i < arr.size() && arr.at(i) <= arr.at(firstDim); i++) {
     
		arr.at(i) == arr.at(firstDim) ? equalFirst++ : lessFirst++;
	}

	int secondDim = (k - lessFirst * arr.size()) / equalFirst;
	vector<int> res{
      arr.at(firstDim), arr.at(secondDim) };
	return res;
}

int main() {
     
	vector<int> arr{
      3, 1, 2 };
	vector<int> pairKth = getPairKth(arr, 5);
	if (!pairKth.empty()) {
     
		cout << "(" << pairKth.at(0) << ", " << pairKth.at(1) << ")" << endl;
	}
	else {
     
		cout << "pairKth.empty() == true" << endl;
	}

	system("pause");
	return 0;
}

시간 복잡 도가 O (N) 인 해법

/*   ：         ，
                  (  BFPRT O(N)           )
                         (     ：O(N))
                  (  BFPRT O(N)           ) 
*/

#include 
#include 
#include 
using namespace std;

// BFPRT           K (  )         O(N)，           
class BFPRT {
     
public:
	int getMinKthByBFPRT(vector<int>& arr, int k, int left, int right) {
     
		if (arr.empty() || k >= arr.size() || left > right || k < left || k > right) {
     
			return -1;
		}
		if (left == right) {
     
			return arr.at(k);
		}
		int pivot = medianOfMedians(arr, left, right);
		vector<int> range = partition(arr, left, right, pivot);
		if (k > range.at(0) && k < range.at(1)) {
     
			return arr.at(k);
		}
		return k <= range.at(0) ? getMinKthByBFPRT(arr, k, left, range.at(0)) :
			getMinKthByBFPRT(arr, k, range.at(1), right);
	}

	int medianOfMedians(vector<int>& arr, int left, int right) {
     
		vector<int> medians;
		int offset = (right - left + 1) % 5 == 0 ? 0 : 1;
		int groupNums = (right - left + 1) / 5 + offset;
		for (int i = 0; i < groupNums; i++) {
     
			int tmpL = left + i * 5;
			int tmpR = tmpL + 5;
			sort(arr.begin() + tmpL, arr.begin() + min(tmpR, right));
			medians.push_back(arr.at(tmpL + ((min(tmpR, right) - tmpL) >> 1)));
		}
		return getMinKthByBFPRT(medians, medians.size() / 2, 0, medians.size() - 1);
	}

	vector<int> partition(vector<int>& arr, int left, int right, int pivot) {
     
		int tmpL = left - 1;
		int tmpR = right + 1;
		int index = left;
		while (index < tmpR) {
     
			if (arr.at(index) < pivot) {
     
				swap(arr, index++, ++tmpL);
			}
			else if (arr.at(index) > pivot) {
     
				swap(arr, index, --tmpR);
			}
			else {
     
				index++;
			}
		}
		vector<int> res{
      tmpL, tmpR };
		return res;
	}

	void swap(vector<int>& arr, int n1, int n2) {
     
		int tmp = arr.at(n1);
		arr.at(n1) = arr.at(n2);
		arr.at(n2) = tmp;
	}
};

//        O(N)
vector<int> getPairKth(vector<int>& arr, int k) {
     
	if (arr.empty() || k < 0 || k >= arr.size() * arr.size()) {
     
		return vector<int>();
	}
	int firstDim = k / arr.size();
	// BFPRT   K          O(N)
	int firstNum = BFPRT().getMinKthByBFPRT(arr, firstDim, 0, arr.size() - 1);

	//                       O(N)
	int lessFirstNums = 0;
	int equalFirstNums = 0;
	for (int i = 0; i < arr.size() && arr.at(i) <= firstNum; i++) {
     
		arr.at(i) == firstNum ? equalFirstNums++ : lessFirstNums++;
	}

	int secondDim = (k - lessFirstNums * arr.size()) / equalFirstNums;
	// BFPRT   K          O(N)
	int secondNum = BFPRT().getMinKthByBFPRT(arr, secondDim, 0, arr.size() - 1);
	vector<int> pairKth{
      firstNum, secondNum };
	return pairKth;
}

int main() {
     
	vector<int> arr{
      3, 1, 2 };
	vector<int> pairKth = getPairKth(arr, 5);
	if (!pairKth.empty()) {
     
		cout << "(" << pairKth.at(0) << ", " << pairKth.at(1) << ")" << endl;
	}
	else {
     
		cout << "pairKth.empty() == true" << endl;
	}

	system("pause");
	return 0;
}

권리 침해 가 있 으 면 삭제 에 연락 하 십시오. 오류 가 있 으 면 지적 해 주 십시오. 감사합니다.