C++ implementation of O of n complexity to find the K large number algorithm example

  • 2020-05-27 06:43:53
  • OfStack

The example of this paper describes the O(n) algorithm for finding the K large number in the complexity of C++. I will share it with you for your reference as follows:

Title: is in 1 set of array (array element is an integer, can be positive or negative can be 0) to find the largest product of the three Numbers, finally output the largest product.

We know from the question that there are only two outcomes:
1) multiply the three largest positive integers;
2) one of the largest positive integers is multiplied by two of the smallest negative Numbers.

So we need to take the product of the three largest Numbers in the array, m, and then multiply it by the two smallest Numbers in the array, and then multiply it by the largest number, n, and then compare m,n, and choose the largest number to be the final result.

Reference code: https: / / www ofstack. com article / 121189. htm

Implementation code:


#include <iostream>
#include <algorithm>
// partition 
int partition(std::vector<int>&vec,int start,int end) {
 int value=vec[end];
 int tail=start-1;
 for(int i=start;i<end;++i){
  if(vec[i]<value){
   tail++;
   std::swap(vec[i],vec[tail]);
  }
 }
 tail++;
 std::swap(vec[tail],vec[end]);
 return tail;
}
long long solve(std::vector<int>&vec,int start,int end,int k) {
 // Fast sort idea, partition, fast sort complexity is O(nlgn), But take the best value to compare only partitioned ones 1 Is, so is O(n)
 int now = partition(vec,start,end);
 if(k < now)
  return solve(vec,start,now-1,k);
 else if(k > now)
  return solve(vec,now+1,end,k);
 else
  return vec[now];
}
int main() {
 int n;// The number of Numbers to compare 
 while(std::cin>>n) {
  std::vector<int> vec_i(n,0);// use vector storage n The number of 
  for(int i = 0; i < n; ++i) {
   std::cin>>vec_i[i];
  }
  int k;
  // The largest number, index for n-1
  k = n - 1;
  long long x1 = solve(vec_i,0, n-1,k);
  // The next largest number, index for n-2
  k = n - 2;
  long long x2 = solve(vec_i,0, n-2,k);
  // The first 3 A large number of 
  k = n - 3;
  long long x3 = solve(vec_i,0, n-3,k);
  long long Ans = x1 * x2 * x3;// One of the biggest 3 Product of Numbers 
  if(n > 3) {
   // The smallest number, index for 0
   k = 0;
   long long y1 = solve(vec_i,0, n-1,k);
   // The next smallest number, index for 1
   k = 1;
   long long y2 = solve(vec_i,0, n-2,k);
   Ans = std::max(Ans, y1*y2*x1);// Let's take the maximum 
  }
  std::cout<<Ans;
 }
 return 0;
}

I hope this article is helpful to you C++ programming.


Related articles: