An array with n elements which is K most sorted, namely the distance between the current index and sorted index is less than K. It should be faster than O(n*lgn).

sort an sorted array

//build an Kth min heap, time k*lgk + (n-k)lgk

  1 #include <iostream>
  2 #include <iterator>
  3 #include <algorithm>
  4 using namespace std;
  5
  6 void shiftdown(int arr[], int root, int right){
  7     int child = 2*root + 1;
  8
  9     if (child < right && (child + 1) < right){
 10             child = (arr[child] < arr[child + 1])? (child + 1): child;
 11     } else {
 12         return;
 13     }
 14
 15     if (arr[root] > arr[child])
 16         return;
 17
 18     swap(arr[root], arr[child]);
 19
 20     shiftdown(arr, child, right);
 21 }
 22
 23 void hSort(int arr[], int size){
 24     for (int index = size/2; index >= 0; --index){
 25         shiftdown(arr, index, size);
 26     }
 27
 28     for (int index = size; index > 0; --index){
 29         swap(arr[0], arr[index]);
 30         shiftdown(arr, 0, index);
 31     }
 32 }
 33
 34 int main(){
 35     int interval = 5;
 36     int array[] = {3, 2, 1, 6, 4, 7, 5, 9, 10, 8};
 37     copy(array,
 38          array + sizeof(array)/sizeof(array[0]),
 39          ostream_iterator<int>(cout, " "));
 40     cout << endl;
 41
 42     hSort(array, interval);
 43     for (int index = 0; index < (sizeof(array)/sizeof(array[0]) - interval); ++interval){
 44         hSort(array + index, interval);
 45     }
 46
 47     copy(array,
 48          array + sizeof(array)/sizeof(array[0]),
 49          ostream_iterator<int>(cout, " "));
 50     cout << endl;
 51     return 0;
 52 }


给定一个数t，以及n个整数，在这n个整数中找到相加之和为t的所有组合，例如t = 4，n = 6，这6个数为[4, 3, 2, 2, 1, 1]，这样输出就有4个不同的组合，它们的相加之和为4：4, 3+1, 2+2, and 2+1+1

int arr[10000];int n;int t; void dfs(int d, int sum, vector<int>& re) {  if (sum < 0 || d == n) {    return ;  }  if (sum == 0) {    for (int i = 0;  i < re.size(); ++i) {      cout << re.at(i) <<  " ";     }    cout << endl;  }   for (int i = d + 1; i < n; ++i) {    re.push_back(arr[i]);    dfs(i, sum - arr[i], re);    re.pop_back();  }} 

void solve(int arr[], int size, int expected, vector<int>& result) {  uint32 end = pow(2, size) - 1;  for (uint32 i = 0; i <= end; ++i) {    uint32 shirt = 1;    int sum  = 0;     for (uint32 j = 0; j < size; ++j) {      if ((shirt & i) != 0) {        sum += arr[j];      }      shirt = shirt << 1;    }    if (expected == sum) {      result.push_back(i);      }  }} void output(uint32 bits, int arr[], int size) {  uint32 shirt = 1;  for (uint32 j = 0; j < size; ++j) {    if ((shirt & bits) != 0) {      cout << arr[j] <<  " ";    }    shirt <<= 1;  }  cout << endl;} int main(int argc, char *argv[]){  int n;  int sum;  cin >> sum;  while (cin >> n && n != 0) {    int* arr = new int[n];    for (int i = 0; i < n; ++i) {      cin >> arr[i];    }        vector<int> result;    solve(arr, n, sum, result);        vector<int>::iterator it = result.begin();    for (; it != result.end(); it++) {      output(*it, arr, n);    }      delete []arr;  }