# 重新排列数组，使索引相同的子集的总和与原始数组中的总和不同

2021年4月30日19:22:18 发表评论 590 次浏览

## 本文概述

A [0] = 1000 B [0] = 100
A [1] = 100 B [1] = 10
A [2] = 10 B [2] = 1
A [3] = 1 B [3] = 1000

{A [0], A [1]} = 1100 {B [0], B [1]} = 110
{A [0], A [2]} = 1010 {B [0], B [2]} = 101
{A [1], A [2]} = 110 {B [1], B [2]} = 11
....

{A [0], A [1], A [2]} = 1110 {B [0], B [1], B [2]} = 111
{A [0], A [2 ], A [3]} = 1011 {B [0], B [2], B [3]} = 1101
{A [1], A [2], A [3]} = 111 {B [1] , B [2], B [3]} = 1011

• 成对存储数组元素{A [i], i}.
• 按升序对对数组元素
• 现在, 遍历排序的顺序, 并将每个元素插入其下一个更大元素的原始索引(即, 在索引处)v [(i + 1)％n]。秒)。这样可以确保除索引之外的每个索引现在都具有比其中存储的先前值小的元素。

## C ++

``````//C++ Program to implement
//the above approach
#include <bits/stdc++.h>
using namespace std;

//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
void printNewArray(vector<int> a, int n)
{
//Initialize a vector
vector<pair<int , int>> v;

//Iterate the array
for ( int i = 0; i <n; i++) {

v.push_back({ a[i], i });
}

//Sort the vector
sort(v.begin(), v.end());

int ans[n];

//Shift of elements to the
//index of its next cyclic element
for ( int i = 0; i <n; i++) {
ans[v[(i + 1) % n].second]
= v[i].first;
}

for ( int i = 0; i <n; i++) {
cout <<ans[i] <<" " ;
}
}

//Driver Code
int main()
{
vector<int> a = { 4, 1, 2, 5, 3 };

int n = a.size();

printNewArray(a, n);

return 0;
}``````

## Java

``````//Java program to implement
//the above approach
import java.io.*;
import java.util.*;

class GFG{

static class pair
{
int first, second;

pair( int first, int second)
{
this .first = first;
this .second = second;
}
}

//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
static void printNewArray(List<Integer> a, int n)
{

//Initialize a vector
List<pair> v = new ArrayList<>();

//Iterate the array
for ( int i = 0 ; i <n; i++)
{
}

//Sort the vector
Collections.sort(v, (pair s1, pair s2) ->
{
return s1.first - s2.first;
});

int ans[] = new int [n];

//Shift of elements to the
//index of its next cyclic element
for ( int i = 0 ; i <n; i++)
{
ans[v.get((i + 1 ) % n).second] = v.get(i).first;
}

for ( int i = 0 ; i <n; i++)
{
System.out.print(ans[i] + " " );
}
}

//Driver Code
public static void main(String args[])
{
List<Integer> a = Arrays.asList( 4 , 1 , 2 , 5 , 3 );

int n = a.size();
printNewArray(a, n);
}
}

//This code is contributed by offbeat``````

## Python3

``````# Python3 Program to implement
# the above approach

# Function to rearrange the array such
# that no same-indexed subset have sum
# equal to that in the original array
def printNewArray(a, n):

# Initialize a vector
v = []

# Iterate the array
for i in range (n):
v.append((a[i], i ))

# Sort the vector
v.sort()

ans = [ 0 ] * n

# Shift of elements to the
# index of its next cyclic element
for i in range (n):
ans[v[(i + 1 ) % n][ 1 ]] = v[i][ 0 ]

for i in range (n):
print (ans[i], end = " " )

# Driver Code
if __name__ = = "__main__" :
a = [ 4 , 1 , 2 , 5 , 3 ]
n = len (a)
printNewArray(a, n)

# This code is contributed by Chitranayal``````

``3 5 1 4 2``